آموزش ریاضیات (Mathematics)
۲۱۷۵ آموزش
نمایش دسته بندی ها (۲۱۷۵ آموزش)

روش QR (انگلیسی : QR Algorithm / QR Method)، در ریاضیات (Mathematics)

انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :

روش QR (انگلیسی : QR Algorithm / QR Method) :

تجزیه

\[ A = QR \]

و تکرار

\[ A_{k+1} = R_k Q_k \]

توضیح ساده: روش QR یکی از مهم ترین و پرکاربردترین الگوریتم ها برای محاسبه همه مقادیر ویژه یک ماتریس است. ایده بسیار زیبا و ساده است: ماتریس A را به حاصل ضرب یک ماتریس متعامد Q و یک ماتریس بالامثلثی R تجزیه می کنیم. سپس ماتریس جدید A' = RQ را می سازیم. این کار را تکرار می کنیم. در طول تکرارها، A به تدریج به یک ماتریس بالامثلثی (یا قطری، اگر متقارن باشد) همگرا می شود که مقادیر ویژه روی قطر آن قرار دارند. این روش برای ماتریس های متراکم تا اندازه چند هزار کارایی دارد.

شرح گام به گام: مراحل اصلی:

۱. ابتدا ماتریس A را با روش هوسهولدر به شکل بالاهسنبرگ (برای نامتقارن) یا سه قطری (برای متقارن) کاهش می دهیم.

۲. سپس تکرار QR را شروع می کنیم:

   برای k = ۱, ۲, ... تا همگرایی:

      Aₖ = Qₖ Rₖ (تجزیه QR)

      Aₖ₊₁ = Rₖ Qₖ

۳. در هر تکرار، Aₖ به شکل بالامثلثی نزدیک تر می شود.

۴. برای تسریع همگرایی، از تغییر مکان (Shift) استفاده می کنیم: Aₖ - μI = Qₖ Rₖ، سپس Aₖ₊₁ = Rₖ Qₖ + μI.

۵. پس از همگرایی، مقادیر ویژه روی قطر Aₖ قرار دارند. بردارهای ویژه را می توان با جمع آوری Qها بدست آورد.

مثال عددی (ساده شده): برای ماتریس A = [[2,1],[1,2]] که قبلا سه قطری است (خودش سه قطری است). تکرار QR: ابتدا A₀ = A. تجزیه QR: با روش گرام-اشمیت یا هوسهولدر. محاسبه: q₁ = (a₁)/||a₁|| = [2,1]/√5 = [0.8944,0.4472] r₁₁ = ||a₁|| = √5 = 2.236 r₁₂ = q₁ᵀ a₂ = [0.8944,0.4472]ᵀ [1,2] = 0.8944*1 + 0.4472*2 = 0.8944+0.8944=1.7888 a₂⊥ = a₂ - r₁₂ q₁ = [1,2] - 1.7888[0.8944,0.4472] = [1-1.6, 2-0.8] = [-0.6, 1.2] (تقریبی) q₂ = a₂⊥/||a₂⊥|| = [-0.6,1.2]/√(0.36+1.44)=[-0.6,1.2]/1.342 = [-0.4472,0.8944] r₂₂ = ||a₂⊥|| = 1.342 بنابراین Q = [[0.8944, -0.4472], [0.4472, 0.8944]]، R = [[2.236, 1.7888], [0, 1.342]] A₁ = R Q = [[2.236, 1.7888], [0, 1.342]] * [[0.8944, -0.4472], [0.4472, 0.8944]] = عنصر (۱,۱): 2.236*0.8944 + 1.7888*0.4472 = 2 + 0.8 = 2.8 عنصر (۱,۲): 2.236*(-0.4472) + 1.7888*0.8944 = -1 + 1.6 = 0.6 عنصر (۲,۱): 0*0.8944 + 1.342*0.4472 = 0.6 عنصر (۲,۲): 0*(-0.4472) + 1.342*0.8944 = 1.2 A₁ = [[2.8, 0.6], [0.6, 1.2]]. این ماتریس به ماتریس قطری نزدیک تر شده. تکرار بعدی بیشتر قطری می شود.

مزایا: بسیار پایدار، همه مقادیر ویژه را همزمان می دهد، برای ماتریس های متراکم تا اندازه متوسط ایده آل است.

معایب: برای ماتریس های بزرگ و تنک مناسب نیست (هزینه O(n³)). نیاز به ذخیره سازی کامل ماتریس دارد.

کاربردها: استانداردترین روش در نرم افزارهای عددی (MATLAB، LAPACK) برای محاسبه مقادیر ویژه ماتریس های متراکم.

نکته: روش QR با تغییر مکان های هوشمندانه، همگرایی بسیار سریعی دارد (معمولا درجه سوم).

نویسنده علیرضا گلمکانی
شماره کلید 8569
گزینه ها
به اشتراک گذاری (Share) در شبکه های اجتماعی
نظرات 0 0 0

ارسال نظر جدید (بدون نیاز به عضو بودن در وب سایت)