روش آرنولدی (Arnoldi Iteration)، در ریاضیات (Mathematics)

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

روش آرنولدی (Arnoldi Iteration) :

توضیح ساده: روش آرنولدی یک روش تکراری برای تقریب مقادیر ویژه و بردارهای ویژه ماتریس های بزرگ و تنک (معمولا نامتقارن) است. این روش یک پایه متعامد برای زیرفضای کرایلف می سازد و ماتریس را به یک ماتریس بالاهسنبرگ کاهشی (کاهش یافته) تبدیل می کند. سپس مقادیر ویژه این ماتریس کوچک، تقریبی از مقادیر ویژه اصلی هستند. این روش پایه ای برای روش های پیشرفته تری مانند GMRES (برای حل دستگاه) و ARPACK (برای مقادیر ویژه) است.

شرح گام به گام: با یک بردار شروع v₁ (معمولا تصادفی) با ||v₁||=1 شروع می کنیم. برای j = ۱, ۲, ..., m:

۱. w = A v_j را محاسبه کن.

۲. برای i = ۱ تا j: h_{i,j} = v_iᵀ w، w = w - h_{i,j} v_i (متعامدسازی گرام-اشمیت)

۳. h_{j+1,j} = ||w||. اگر h_{j+1,j} = 0، توقف (زیرفضا پایا شده).

۴. v_{j+1} = w / h_{j+1,j}

در پایان، ماتریس H_m (از مرتبه m×m) یک ماتریس بالاهسنبرگ است که تقریبی از A در زیرفضای کرایلف است. مقادیر ویژه H_m (که مقادیر ویژه آرنولدی نامیده می شوند) تقریبی از مقادیر ویژه A هستند.

مثال عددی: برای ماتریس A = [[2,1,0],[1,2,1],[0,1,2]]، با v₁ = [1,0,0]ᵀ: j=1: w = A v₁ = [2,1,0]ᵀ. h₁₁ = v₁ᵀ w = 2. w = w - 2v₁ = [0,1,0]ᵀ. h₂₁ = ||w|| = 1. v₂ = [0,1,0]ᵀ. j=2: w = A v₂ = [1,2,1]ᵀ. h₁₂ = v₁ᵀ w = 1. w = w - 1*v₁ = [0,2,1]ᵀ. h₂₂ = v₂ᵀ w = 2. w = w - 2*v₂ = [0,0,1]ᵀ. h₃₂ = ||w|| = 1. v₃ = [0,0,1]ᵀ. j=3: w = A v₃ = [0,1,2]ᵀ. h₁₃ = v₁ᵀ w = 0. w = w - 0*v₁ = [0,1,2]. h₂₃ = v₂ᵀ w = 1. w = w - 1*v₂ = [0,0,2]. h₃₃ = v₃ᵀ w = 2. w = w - 2*v₃ = 0. h₄₃ = 0. توقف. ماتریس H = [[2,1,0],[1,2,1],[0,1,2]] که خود A است! چون m=n و زیرفضا کل فضا را پوشش داده.

مزایا: مناسب برای ماتریس های بزرگ و تنک، فقط نیاز به ضرب ماتریس در بردار دارد، حافظه قابل کنترل (با انتخاب m مناسب).

معایب: با افزایش m، هزینه و حافظه افزایش می یابد. معمولا با راه اندازی مجدد (Restarted Arnoldi) استفاده می شود. ممکن است دچار از دست دادن متعامد بودن به دلیل خطای گرد کردن شود.

کاربردها: در دینامیک سیالات محاسباتی، در تحلیل سازه ها، در شیمی کوانتومی، در هر جایی که با ماتریس های بزرگ و تنک روبرو هستیم.

نکته: روش آرنولدی پایه و اساس نرم افزار معروف ARPACK است که برای محاسبه مقادیر ویژه ماتریس های بزرگ استفاده می شود.