پرش به ناوبریپرش به جستجو

در ریاضیات ، تکرار توان (که به آن روش قدرت نیز گفته می شود ) یک الگوریتم ارزش ویژه است : با توجه به ماتریس مورب آ، الگوریتم یک عدد تولید می کند \ لامبدا ، که بزرگترین (در مقدار مطلق) ارزش ویژه از استآ، و یک بردار غیر صفر v، که یک بردار ویژه مربوط به\ لامبدا ، به این معنا که، {\ displaystyle Av = \ lambda v}. این الگوریتم به تکرار Von Mises نیز معروف است . [1]

تکرار نیرو یک الگوریتم بسیار ساده است ، اما ممکن است به آرامی همگرا شود. وقت گیرترین کار الگوریتم ضرب ماتریس استآتوسط یک بردار ، بنابراین برای یک ماتریس پراکنده بسیار بزرگ با اجرای مناسب موثر است.

 

فهرست

روش [ ویرایش ]

انیمیشنی که الگوریتم تکرار توان را در ماتریس 2x2 تجسم می کند. ماتریس توسط دو بردار ویژه آن به تصویر کشیده شده است. خطا به عنوان محاسبه می شود{\ displaystyle || {\ text {تقریبی}} - {\ text {بزرگترین بردار ویژه}} ||}

الگوریتم تکرار توان با بردار شروع می شود b_ {0}، که ممکن است یک تقریب با بردار ویژه غالب یا یک بردار تصادفی باشد. روش با رابطه عود توصیف می شود

{\ displaystyle b_ {k + 1} = {\ frac {Ab_ {k}} {\ | Ab_ {k} \ |}}}

بنابراین ، در هر تکرار ، بردار b_ {k} در ماتریس ضرب می شود آ و عادی شده

اگر فرض کنیم آ دارای یک ارزش ویژه است که از نظر شدت کاملاً بزرگتر از سایر مقادیر ویژه آن و بردار شروع است b_ {0} دارای یک جز non غیر صفر در جهت یک بردار ویژه مرتبط با مقدار ویژه غالب است ، سپس یک دنباله \ چپ (b _ {{k}} \ راست) همگرا می شود به یک بردار ویژه مرتبط با ارزش ویژه غالب.

بدون دو فرض بالا ، توالی \ چپ (b _ {{k}} \ راست)لزوماً همگرا نمی شود. در این سکانس ،

b_k = e ^ {i \ phi_k} v_1 + r_k،

جایی که v_ {1} یک بردار ویژه است که با ارزش ویژه غالب مرتبط است ، و \ | r _ {{k}} \ | \ rightarrow 0. حضور اصطلاحe ^ {{i \ phi _ {{k}}}} دلالت دارد \ چپ (b _ {{k}} \ راست) همگرایی نمی کند مگر اینکه e ^ {{i \ phi _ {{k}}}} = 1. تحت دو فرض ذکر شده در بالا ، دنباله\ چپ (\ mu _ {{k}} \ راست) تعریف شده توسط

\ mu _ {{k}} = {\ frac {b _ {{k}} ^ {{*}} Ab _ {{k}}} {b _ {{k}} ^ {{*}} b _ {{k} }}}

با ارزش ویژه غالب همگرا می شود (با ضریب ریلی ). [ توضیحات لازم است ]

یکی می تواند این را با الگوریتم زیر محاسبه کند (در پایتون با NumPy نشان داده شده است):

#! / usr / bin / env python3

وارد کردن  numpy  به عنوان  np

دف  power_iteration ( ، num_simulations : INT ): # در حالت ایده آل را انتخاب نمایید یک بردار تصادفی # برای کاهش شانس است که بردار # متعامد به بردارهای ویژه است b_k = NP . تصادفی . رند ( . شکل [ 1 ])  
    
    
    
      

    for  _  in  range ( num_simulations ): 
        # محاسبه محصول ماتریس توسط بردار Ab 
        b_k1  =  np . نقطه ( A ،  b_k )

        # محاسبه هنجار 
        b_k1_norm  =  np . linalg . هنجار ( b_k1 )

        # بردار 
        b_k  =  b_k1  /  b_k1_norm را عادی کنید

    بازگشت  b_k

power_iteration ( NP . آرایه ([[ 0.5 ،  0.5 ]،  [ 0.2 ،  0.8 ]])،  10 )

بردار b_ {k}به یک بردار ویژه مرتبط در حالت ایده آل ، باید از ضریب Rayleigh برای بدست آوردن مقدار ویژه مربوطه استفاده کرد.

این الگوریتم برای محاسبه Google PageRank استفاده می شود .

از این روش می توان برای محاسبه شعاع طیفی (مقدار ویژه با بیشترین اندازه برای ماتریس مربع) با محاسبه ضریب Rayleigh استفاده کرد.

{\ displaystyle \ rho (A) = \ max \ left \ {| \ lambda _ {1} |، \ dotsc، | \ lambda _ {n} | \ right \} = {\ frac {b_ {k} ^ { \ top} Ab_ {k}} {b_ {k} ^ {\ top} b_ {k}}} = {\ frac {b_ {k + 1} ^ {\ top} b_ {k}} {b_ {k} ^ {\ top} b_ {k}}}.}

تحلیل [ ویرایش ]

اجازه دهید آبه شکل متعارف اردن تجزیه می شود :A = VJV ^ {{- 1}}، جایی که اولین ستون از V یک بردار ویژه از است آ مربوط به ارزش ویژه مسلط \ lambda _ {{1}}. از آنجا که ارزش ویژه مسلط بهآ منحصر به فرد است ، اولین بلوک اردن از ج هست 1 \ بار 1 ماتریس {\ displaystyle [\ lambda _ {1}] ،} جایی که \ lambda _ {{1}}بزرگترین مقدار ویژه A از نظر اندازه است. بردار شروعb_ {0}می توان به عنوان یک ترکیب خطی از ستون های V نوشت :

{\ displaystyle b_ {0} = c_ {1} v_ {1} + c_ {2} v_ {2} + \ cdots + c_ {n} v_ {n}.}

با فرض ، ب _ {{0}} دارای یک جز non غیر صفر در جهت ارزش ویژه غالب است ، بنابراین c _ {{1}} \ neq 0.

رابطه عود محاسباتی مفید برایb _ {{k + 1}} می تواند به صورت زیر بازنویسی شود:

{\ displaystyle b_ {k + 1} = {\ frac {Ab_ {k}} {\ | Ab_ {k} \ |}} = {\ frac {A ^ {k + 1} b_ {0}} {\ | A ^ {k + 1} b_ {0} \ |}} ،}

که در آن عبارت: {\ frac {A ^ {{k + 1}} b _ {{0}}} {\ | A ^ {{k + 1}} b _ {{0}} \ |}} بیشتر قابل تجزیه و تحلیل است.

{\ displaystyle {\ start {تراز شده} b_ {k} & = {\ frac {A ^ {k} b_ {0}} {\ | A ^ {k} b_ {0} \ |}} \\ & = {{ \ frac {\ چپ (VJV ^ {- 1} \ راست) ^ {k} b_ {0}} {\ | \ چپ (VJV ^ {- 1} \ راست) ^ {k} b_ {0} \ |} } \\ & = {\ frac {VJ ^ {k} V ^ {- 1} b_ {0}} {\ | VJ ^ {k} V ^ {- 1} b_ {0} \ |}} \\ & = {\ frac {VJ ^ {k} V ^ {- 1} \ چپ (c_ {1} v_ {1} + c_ {2} v_ {2} + \ cdots + c_ {n} v_ {n} \ سمت راست )} {\ | VJ ^ {k} V ^ {- 1} \ چپ (c_ {1} v_ {1} + c_ {2} v_ {2} + \ cdots + c_ {n} v_ {n} \ سمت راست ) \ |}} \\ & = {\ frac {VJ ^ {k} \ سمت چپ (c_ {1} e_ {1} + c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ راست)} {\ | VJ ^ {k} \ چپ (c_ {1} e_ {1} + c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ سمت راست) \ |} } \\ &= \ چپ ({\ frac {\ lambda _ {1}} {| \ lambda _ {1} |}} \ راست) ^ {k} {\ frac {c_ {1}} {| c_ {1} |} } {\ frac {v_ {1} + {\ frac {1} {c_ {1}}} V \ چپ ({\ frac {1} {\ lambda _ {1}}} J \ راست) ^ {k} \ چپ (c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ راست)} {\ چپ \ | v_ {1} + {\ frac {1} {c_ {1}}} V \ چپ ({\ frac {1} {\ lambda _ {1}}} J \ راست) ^ {k} \ چپ (c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ راست) \ راست \ |}} \ پایان {تراز شده}}}

عبارت فوق ساده به صورت {\ displaystyle k \ to \ infty}

{\ displaystyle \ left ({\ frac {1} {\ lambda _ {1}}} J \ right) ^ {k} = {\ start {bmatrix} [1] &&&& \\ & \ left ({\ frac { 1} {\ lambda _ {1}}} J_ {2} \ راست) ^ {k} &&& \\ && \ ddots & \\ &&& \ چپ ({\ frac {1} {\ lambda _ {1}}} J_ {m} \ right) ^ {k} \\\ end {bmatrix}} \ rightarrow {\ start {bmatrix} 1 &&&& \\ & 0 &&& \\ && \ ddots & \\ &&& 0 \\\ end {bmatrix}} \ quad {\ text {as}} \ quad k \ to \ invyy.}

این حد از این واقعیت حاصل می شود که مقدار ویژه از {\ frac {1} {\ lambda _ {{1}}}} J _ {{i}} کمتر از 1 است ، بنابراین

{\ displaystyle \ left ({\ frac {1} {\ lambda _ {1}}} J_ {i} \ right) ^ {k} \ to 0 \ quad {\ text {as}} \ quad k \ to \ بی ارزش.}

نتیجه می شود که:

{\ displaystyle {\ frac {1} {c_ {1}}} V \ چپ ({\ frac {1} {\ lambda _ {1}}} J \ راست) ^ {k} \ چپ (c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ right) \ to 0 \ quad {\ text {as}} \ quad k \ to \ infty}

با استفاده از این واقعیت ، ب _ {{k}} را می توان به شکلی نوشت که بر رابطه آن با تأکید دارد v _ {{1}}وقتی k بزرگ است:

{\ displaystyle {\ start {تراز شده} b_ {k} & = \ چپ ({\ frac {\ lambda _ {1}} {| \ lambda _ {1} |}} \ راست) ^ {k} {\ frac {c_ {1}} {| c_ {1} |}} {\ frac {v_ {1} + {\ frac {1} {c_ {1}}} V \ چپ ({\ frac {1} {\ lambda _ {1}}} J \ راست) ^ {k} \ چپ (c_ {2} e_ {2} + \ cdots + c_ {n} e_ {n} \ سمت راست)} {\ چپ \ | v_ {1} + {\ frac {1} {c_ {1}}} V \ چپ ({\ frac {1} {\ lambda _ {1}}} J \ راست) ^ {k} \ چپ (c_ {2} e_ { 2} + \ cdots + c_ {n} e_ {n} \ right) \ right \ |}} \\ [6pt] & = e ^ {i \ phi _ {k}} {\ frac {c_ {1}} {| c_ {1} |}} {\ frac {v_ {1}} {\ | v_ {1} \ |}} + r_ {k} \ end {تراز شده}}}

جایی که {\ displaystyle e ^ {i \ phi _ {k}} = \ left (\ lambda _ {1} / | \ lambda _ {1} | \ right) ^ {k}} و {\ displaystyle \ | r_ {k} \ | \ تا 0} مانند {\ displaystyle k \ to \ infty}

تسلسل و توالی \ چپ (b _ {{k}} \ راست)محدود است ، بنابراین شامل یک دنباله همگرا است. توجه داشته باشید که بردار ویژه مربوط به مقدار ویژه غالب فقط تا یک مقیاس منحصر به فرد است ، بنابراین اگرچه توالی\ چپ (b _ {{k}} \ راست) ممکن است همگرا نشود ، ب _ {{k}}تقریباً یک بردار ویژه A برای k بزرگ است .

متناوباً ، اگر A قابل مورب باشد ، اثبات زیر همان نتیجه را دارد

اجازه دهید λ 1 ، λ 2 ، ...، λ متر باشد متر مقادیر ویژه (شمارش، با تعدد) از و اجازه دهید V 1 ، V 2 ، ...، V متر باشد بردارهای ویژه مربوطه. فرض کنید که\ lambda _ {1} ارزش ویژه غالب است ، به طوری که | \ lambda _ {1} |> | \ lambda _ {j} | برای j> 1.

بردار اولیه b_ {0} می توان نوشت:

b_ {0} = c _ {{1}} v _ {{1}} + c _ {{2}} v _ {{2}} + \ cdots + c _ {{m}} v _ {{m}}.

اگر b_ {0}به صورت تصادفی (با احتمال یکنواخت) و سپس c 1 ≠ 0 با احتمال 1 انتخاب می شود . اکنون،

{\ displaystyle {\ start {تراز شده} A ^ {k} b_ {0} & = c_ {1} A ^ {k} v_ {1} + c_ {2} A ^ {k} v_ {2} + \ cdots + c_ {m} A ^ {k} v_ {m} \\ & = c_ {1} \ lambda _ {1} ^ {k} v_ {1} + c_ {2} \ lambda _ {2} ^ {k } v_ {2} + \ cdots + c_ {m} \ lambda _ {m} ^ {k} v_ {m} \\ & = c_ {1} \ lambda _ {1} ^ {k} \ سمت چپ (v_ { 1} + {\ frac {c_ {2}} {c_ {1}}} \ چپ ({\ frac {\ lambda _ {2}} {\ lambda _ {1}}} \ راست) ^ {k} v_ {2} + \ cdots + {\ frac {c_ {m}} {c_ {1}}} \ چپ ({\ frac {\ lambda _ {m}} {\ lambda _ {1}}} \ راست) ^ {k} v_ {m} \ right) \\ & \ to c_ {1} \ lambda _ {1} ^ {k} v_ {1} && \ left | {\ frac {\ lambda _ {j}} {\ lambda _ {1}}} \ right | <1 {\ text {for}} j> 1 \ end {تراز شده}}}

از سوی دیگر:

{\ displaystyle b_ {k} = {\ frac {A ^ {k} b_ {0}} {\ | A ^ {k} b_ {0} \ |}}.}

از این رو، b_ {k} به (چند برابر) بردار ویژه همگرا می شود v_ {1}. همگرایی هندسی و با نسبت است

\ چپ | {\ frac {\ lambda _ {2}} {\ lambda _ {1}}} \ راست | ،

جایی که \ lambda _ {2}دومین ارزش ویژه مسلط است. بنابراین ، اگر یک مقدار ویژه نزدیک به مقدار ویژه غالب وجود داشته باشد ، روش به آرامی همگرا می شود.

برنامه ها [ ویرایش ]

اگرچه روش تکرار نیرو فقط یک مقدار ویژه از یک ماتریس را تقریب می زند ، اما برای برخی از مشکلات محاسباتی همچنان مفید است . به عنوان مثال ، Google از آن برای محاسبه اسناد PageRank در موتور جستجوی خود استفاده می کند [2] و توییتر از آن برای نشان دادن توصیه های کاربران به دنبال استفاده از آنها استفاده می کند. [3] روش تکرار توان به ویژه برای ماتریس های پراکنده ، مانند ماتریس وب ، یا به عنوان روش بدون ماتریس که نیازی به ذخیره ماتریس ضریب نیست ، مناسب است.آ صریحاً ، اما درعوض می تواند به یک عملکرد ارزیابی محصولات بردار ماتریس دسترسی پیدا کند تبر. برای ماتریس های غیر متقارن که به خوبی شرطی شده اند ، روش تکرار نیرو می تواند از تکرار پیچیده تر Arnoldi بهتر باشد. برای ماتریس های متقارن ، از روش تکرار توان به ندرت استفاده می شود ، زیرا سرعت همگرایی آن می تواند به راحتی افزایش یابد بدون اینکه هزینه کمی برای هر تکرار کاهش یابد. به عنوان مثال ، تکرار Lanczos و LOBPCG را ببینید .

برخی از الگوریتم های پیشرفته ارزش ویژه پیشرفته تر را می توان به عنوان تغییرات تکرار توان درک کرد. به عنوان مثال ، روش تکرار معکوس تکرار توان را به ماتریس اعمال می کندA ^ {- 1}. الگوریتم های دیگر کل زیر فضای تولید شده توسط بردارها را بررسی می کنندb_ {k}. این زیرفضا به زیر فضایی کریلوف معروف است . با تکرار Arnoldi یا تکرار Lanczos قابل محاسبه است .

 

منبع

https://en.wikipedia.org/wiki/Power_iteration