ادامه تجزیه چولسکی

توسط علی رضا نقش نیلچی | دوشنبه بیست و سوم تیر ۱۳۹۹ | 23:17

تجزیه LDL [ ویرایش ]

یک شکل جایگزین ، حذف نیاز به ریشه های مربعی هنگامی که A متقارن باشد ، عامل بندی نامشخص متقارن است [12]

$\ displaystyle {\ fill {تراز شده} \ mathbf {A} = \ mathbf {LDL ^ {\ mathrm {T}} & = {\ fill pmatrix} 1 & 0 & 0 \\ L_ {21} & 1 & 0 \\ L_ {31} & L_ {32} & 1 \\\ end {pmatrix}} {\ fill {pmatrix} D_ {1} & 0 & 0 \\ 0 & D_ {2} & 0 \\ 0 & 0 & D_ {3} \** end {pmatrix}} {\ fill {pmatrix } 1 & L_ {21} & L_ {31} \\ 0 & 1 & L_ {32} \\ 0 & 0 & 1 \\ end {pmatrix}} \\ & = {\ fill pmatrix} D_ {1 && (\ mathrm {متقارن}) \\ L_ {21} D_ {1} & L_ {21} ^ {2} D_ {1} + D_ {2} & \\ L_ {31} D_ {1} & L_ {31} L_ {21} D_ {1} + L_ {32} D_ {2} & L_ {31} ^ {2} D_ {1} + L_ {32} ^ {2} D_ {2} + D_ {3}. \ end {pmatrix}}. \ end {تراز شده} }$

روابط بازگشتی زیر برای ورود D و L اعمال می شود :

$\ displaystyle D_ {j} = A_ {jj} - \ sum _ {k = 1} ^ {j-1} L_ {jk} ^ {2} D_ {k}،$

$left \ displaystyle L_ {ij} = {\ frac {1} {D_ {j}}} \ left (A_ {ij} - \ sum _ {k = 1} ^ {j-1} L_ {ik} L_ {jk D_ {k} \ درست) \ quad {\ متن {برای}} i> j.}$

این کار تا زمانی ادامه می یابد که عناصر مورب تولید شده در D بدون صفر بمانند. تجزیه پس از آن منحصر به فرد است. D و L واقعی اگر واقعی است.

برای ماتریس پیچیده هرمیتی A ، فرمول زیر اعمال می شود:

$\ displaystyle D_ {j} = A_ {jj} - \ sum _ {k = 1} ^ {j-1} L_ {jk} L_ {jk} ^ {*} D_ {k}،}$

$left \ displaystyle L_ {ij} = {\ frac {1} {D_ {j}}} \ left (A_ {ij} - \ sum _ {k = 1} ^ {j-1} L_ {ik} L_ {jk } ^ {*} D_ {k} \ درست) \ quad {\ متن {برای}} i> j.}$

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

نوع بلوک [ ویرایش ]

هنگامی که در ماتریس نامشخص استفاده می شود ، فاکتورسازی LDL * بدون محور دقیق دقت ناپایدار است. [13] به طور خاص ، عناصر عامل پذیری می توانند خودسرانه رشد کنند. بهبود احتمالی اجرای فاکتورسازی در ماتریسهای زیر بلوک است که معمولاً 2 � 2 است: [14]

$\ displaystyle {\ fill {تراز شده} \ mathbf {A} = \ mathbf {LDL ^ {\ mathrm {T}} & = {\ fill pmatrix} \ mathbf {I} & 0 & 0 \ 0 mathbf {L} _ {21} & \ mathbf {I} & 0 \\\ mathbf {L} _ {31} & \ mathbf {L} _ {32} & \ mathbf {I} \\\ end pmatrix}} {\ fill {pmatrix \ mathbf {D} _ {1} & 0 & 0 \\ 0 & \ mathbf {D} _ {2} & 0 \\ 0 & 0 & \ mathbf {D} _ {3} \** end {pmatrix}} {\ fill {pmatrix} \ mathbf {I} & \ mathbf {L} _ {21} ^ {\ mathrm {T}} & \ mathbf {L} _ {31} ^ {\ mathrm {T}} \\ 0 & \ mathbf {I} & \ mathbf {L} _ {32} ^ {\ mathrm {T} \ \\ 0 & 0 & \ mathbf {I} \\\ end {pmatrix}} \\ & = {\ start pmatrix} \ mathbf {D} _ { 1 }&& (\ mathrm {متقارن) \\\ mathbf {L} _ {21 \ mathbf {D} _ {1} & \ mathbf {L} _ {21} \ mathbf {D} _ {1} \ mathbf {L} _ {21} ^ {\ mathrm {T}} + \ mathbf {D} _ {2} & \\\ mathbf {L} _ {31} \ mathbf {D} _ {1} &\ mathbf {L} _ {31} \ mathbf {D} _ {1} \ mathbf {L} _ {21} ^ {\ mathrm {T}} + \ mathbf {L} _ {32} \ mathbf {D} _ {2} & \ mathbf {L} _ {31} \ mathbf {D} _ {1} \ mathbf {L} _ {31} ^ {\ mathrm {T}} + \ mathbf {L} _ {32} \ mathbf {D} _ {2} \ mathbf {L} _ {32} ^ {\ mathrm {T}} + \ mathbf {D} _ {3} \ end {pmatrix}}، \ end {تراز شده}}}$

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

$\ displaystyle \ mathbf {D} _ {j} = \ mathbf {A} _ {jj} - \ sum _ {k = 1} ^ {j-1} \ mathbf {L} _ {jk} \ mathbf {D _ {k} \ mathbf {L} _ {jk} ^ {\ mathrm {T}}،$

$\ displaystyle \ mathbf {L} _ {ij} = \ left (\ mathbf {A} _ {ij} - \ sum _ {k = 1} ^ {j-1 \ mathbf {L} _ {ik} \ mathbf {D} _ {k} \ mathbf {L} _ {jk} ^ {\ mathrm {T}} \ Right) \ mathbf {D} _ {j} ^ {- 1}.$

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

به روزرسانی تجزیه [ ویرایش ]

وظیفه ای که اغلب در عمل بوجود می آید این است که فرد باید تجزیه Cholesky را به روز کند. در جزییات بیشتر ، یک نفر قبلاً تجزیه Cholesky را محاسبه کرده است

$\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^ {*}}$ برخی از ماتریس

$\ mathbf {A$ سپس یکی ماتریس را تغییر می دهد

$\ mathbf {A$ به نوعی بگویید $\ tilde {\ mathbf {A}}$ ، و یکی می خواهد تجزیه Cholesky ماتریس به روز شده را محاسبه کند: $\ tilde {\ mathbf {A}}} = {\ tilde {\ mathbf {L}}} {\ tilde {\ mathbf {L}}} ^ {*}$ . حال این سؤال مطرح است که آیا می توان از تجزیه چولسکی استفاده کرد؟

$\ mathbf {A$ که قبل از محاسبه برای تجزیه Cholesky محاسبه شد $\ tilde {\ mathbf {A}}$ .

مرتباً یک به روزرسانی [ ویرایش ]

مورد خاص ، که در آن ماتریس به روز شده است $\ tilde {\ mathbf {A}}$ مربوط به ماتریس است

$\ mathbf {A$ توسط $\ tilde {\ mathbf {A}}} = \ mathbf {A} + \ mathbf x} \ mathbf x} ^ {*}$ ، به عنوان یک به روزرسانی درجه یک شناخته می شود .

در اینجا یک تابع کوچک [15] با نحوی Matlab نوشته شده است که یک بروزرسانی درجه یک را تحقق می بخشد:

تابع  [L] = cholupdate ( L ، x ) 
    n  =  طول ( x )؛
    برای k = 1: n
        r  =  sqrt ( L ( k ،  k ) ^ 2     x ( k ) ^ 2 )؛ 
        c  =  r  /  L ( k ،  k )؛ 
        s  =  x ( k )  /  L ( k ،  k )؛ 
        L ( k ،  k )  =  r ؛
        اگر k 
            L (( k   1 ): n ،  k )  =  ( L (( k   1 ): n ،  k )     s  *  x (( k   1 ): n ))  /  c ؛ 
            x (( k   1 ): n )  =  c  *  x (( k   1 ): n )  -  s  *  L ((k   1 ): n ،  k )؛
        پایان 
پایان    
پایان

رتبه بندی یک نزولی [ ویرایش ]

downdate رتبه یک شبیه به یک رتبه یک به روز رسانی است، به جز که علاوه بر تفریق است جایگزین: $\ tilde {\ mathbf {A}}} = \ mathbf {A} - \ mathbf {x} \ mathbf x} ^ {*}$ . این تنها در صورت ماتریس جدید کار می کند $\ tilde {\ mathbf {A}}$ هنوز قطعی مثبت است

کد برای به روزرسانی درجه یک که در بالا نشان داده شده است به راحتی می تواند برای انجام یک نزولی رتبه یک باشد: یکی فقط نیاز به جایگزینی دو اضافات در انتساب به r و L((k 1):n, k) تفریق دارد.

اضافه کردن و حذف سطرها و ستون ها [ ویرایش ]

در صورت داشتن ماتریس مشخص و متقارن و مثبت $\ displaystyle \ mathbf {A}$ به صورت بلوک به عنوان نشان داده شده است

$\ displaystyle \ mathbf {A = {\ آغاز {pmatrix} \ mathbf {A} _ {11} & \ mathbf {A} _ {13 \\\ mathbf {A} _ {13} ^ {\ mathrm { T}} & \ mathbf {A} _ {33} \\\ end {pmatrix}}$

و عامل بالایی آن Cholesky است

$\ displaystyle \ mathbf {L} = {\ fill {pmatrix \ mathbf {L} _ {11} & \ mathbf {L} _ {13 \\ 0 & \ mathbf {L} _ {33} \** end {pmatrix} ،}$

سپس برای یک ماتریس جدید $\ tilde {\ mathbf {A}}$ ، که همان است $\ displaystyle \ mathbf {A}$ اما با درج ردیف ها و ستون های جدید ،

$\ displaystyle {\ شروع {تراز شده} {\ tilde {\ mathbf {A}}} & = {\ آغاز {pmatrix} \ mathbf {A _ {11} & \ mathbf {A} _ {12} & \ mathbf {A} _ {13} \\\ mathbf {A} _ {12} ^ {\ mathrm {T}} & \ mathbf {A} _ {22 & \ mathbf {A} _ {23} \\\ mathbf A} _ {13} ^ {\ mathrm {T}} & \ mathbf {A} _ {23} ^ {\ mathrm {T}} & \ mathbf {A} _ {33} \** end {pmatrix} } \ end {تراز شده}}}$

ما علاقه مند به یافتن فاکتورسازی Cholesky از $\ tilde {\ mathbf {A}}$ ، که ما آن را صدا می کنیم $\ displaystyle \ tilde {\ mathbf {S}}}$ بدون محاسبه مستقیم کل تجزیه.

$\ displaystyle {\ شروع {تراز شده} {\ tilde {\ mathbf {S}}} & = {\ آغاز {pmatrix} \ mathbf {S} _ {11} & \ mathbf {S} _ {12} & \ mathbf {S} _ {13} \\ 0 & \ mathbf {S} _ {22} & \ mathbf {S} _ {23} \\ 0 & 0 & \ mathbf {S} _ {33 \\\ end {pmatrix}. \ end {تراز شده}}}$

نوشتن $\ displaystyle \ mathbf {A} \ setminus \ mathbf {b}$ برای راه حل

$\ displaystyle \ mathbf {A} \ mathbf {x} = \ mathbf {b$ ، که می توان به راحتی برای ماتریس های مثلثی پیدا کرد ، و $\ displaystyle \ متن {chol}} (\ mathbf {M})}$ برای تجزیه Cholesky از ${\ mathbf M$ روابط زیر را می توان یافت:

$\ displaystyle {\ شروع {تراز شده} \ mathbf {S} _ {11} & = \ mathbf {L} _ {11} ، \\\ mathbf {S} _ {12} & = \ mathbf {L} _ { 11} ^ {\ mathrm {T}} \ setminus \ mathbf {A} _ {12}، \\\ mathbf {S} _ {13} & = = mathbf {L} _ {13}، \\\ mathbf { S} _ {22} & = {\ text {chol}} (\ mathbf {A} _ {22} - \ mathbf {S} _ {12} ^ {\ mathrm {T}} \ mathbf {S} _ 12}) ، \\\ mathbf {S} _ {23} & = \ mathbf {S} _ {22} ^ {\ mathrm {T}} \ setminus (\ mathbf {A} _ {23} - \ mathbf { S} _ {12} ^ {\ mathrm {T}} \ mathbf {S} _ {13})، \\\ mathbf {S} _ {33} & = {\ text {chol}} (\ mathbf {L } _ {33} ^ {\ mathrm {T}} \ mathbf {L} _ {33} - \ mathbf {S} _ {23} ^ {\ mathrm {T}} \ mathbf {S} _ {23}) . \\\ end {تراز شده}}}$

در صورت تنظیم مناسب ابعاد سطر و ستون (از جمله به صفر) ممکن است از این فرمولها برای تعیین فاکتور چولسکی پس از درج سطرها یا ستونها در هر موقعیت استفاده شود. مشکل معکوس ، وقتی که داریم

با تجزیه شناخته شده Cholesky

و آرزو می کنیم فاکتور چولسکی را تعیین کنیم

$\ displaystyle {\ fill {تراز شده} \ mathbf {L} & = {\ fill pmatrix \ mathbf {L} _ {11} & \ mathbf {L} _ {13} \\ 0 & \ mathbf {L} _ {33} \\\ end {pmatrix}} \ end {تراز شده}}$

ماتریس $\ displaystyle \ mathbf {A}$ با حذف ردیف ها و ستون ها ،

$\ displaystyle {\ fill {تراز شده} \ mathbf {A} & = {\ fill pmatrix} \ mathbf {A _ {11} & \ mathbf {A} _ {13} \\\ mathbf {A} _ { 13} ^ {\ mathrm {T}} & \ mathbf {A} _ {33} \\\ end {pmatrix}}، \ end {تراز شده}}$

قوانین زیر را ارائه می دهد:

$\ displaystyle {\ شروع {تراز شده} \ mathbf {L} _ {11} & = \ mathbf {S} _ {11}، \\\ mathbf {L} _ {13} & = \ mathbf {S} _ 13} ، \\\ mathbf {L} _ {33} & = {\ text {chol}} (\ mathbf {S} _ {33} + \ mathbf {S} _ {23} ^ {\ mathrm {T } \ mathbf {S} _ {23}). \ end {تراز شده}}}$

توجه کنید که معادلات فوق که شامل یافتن تجزیه Cholesky یک ماتریس جدید هستند ، همه از این شکل هستند

$\ displaystyle {\ tilde {\ mathbf {A}}} = \ mathbf {A} \ pm \ mathbf {x} \ mathbf {x} ^ {*}}$ ، که به آنها اجازه می دهد تا با استفاده از روشهای به روزرسانی و downdate که به تفصیل در قسمت قبلی شرح داده شده ، محاسبه شوند. [16]

اثبات ماتریسهای نیمه قطعی مثبت [ ویرایش ]

اثبات با محدود کردن استدلال [ ویرایش ]

الگوریتم های فوق نشان می دهد که هر ماتریس مشخص مثبت است $\ mathbf {A$ تجزیه Cholesky است. این نتیجه را می توان با یک استدلال محدود به پرونده نیمه نهایی قطعی مثبت افزایش داد. این استدلال کاملاً سازنده نیست ، یعنی هیچ محاسبه ای صریح برای محاسبه فاکتورهای چولسکی ارائه نمی دهد.

اگر $\ mathbf {A$ هست یک $n \ n n$ ماتریس نیمه قطعی مثبت ، سپس دنباله $\ displaystyle \ left (\ mathbf {A} _ {k} \ Right) _ {k}: = \ left (\ mathbf {A} + {\ frac {1} {k}} \ mathbf {I} _ { n} \ درست) _ {k}}$ متشکل از ماتریس های مثبت مثبت است . (این یک نتیجه فوری مثلاً قضیه نقشه برداری طیفی برای حساب کارکردی چند جمله ای است.) همچنین ،

$\ displaystyle \ mathbf {A} _ {k} \ rightarrow \ mathbf {A} \ quad {\ متن {برای}} \ quad k \ rightarrow \ infty$

در هنجار اپراتور . از مورد قطعی مثبت ، هر کدام

${\ mathbf {A}} _ {k}$ تجزیه Cholesky است $\ displaystyle \ mathbf {A} _ {k} = \ mathbf {L} _ {k} \ mathbf {L} _ {k} ^ {*}}$ . براساس ویژگی هنجار اپراتور ،

$\ displaystyle \ | \ mathbf {L} _ {k} \ | ^ {2} \ geq \ | \ mathbf {L} _ {k} \ mathbf {L} _ {k} ^ {*} \ | = \ | \ mathbf {A} _ {k} \ | \،.$

بنابراین ${\ نمایش صفحه \ سمت چپ (\ mathbf {L} _ {k} \ سمت راست) _ {k}}$ یک مجموعه محدود در فضای Banach اپراتورها است ، بنابراین نسبتاً جمع و جور است (زیرا فضای بردار زیرین متناهی است). در نتیجه ، این یک پیامد همگرایی دارد ، که از آن نیز یاد شده است ${\ نمایش صفحه \ سمت چپ (\ mathbf {L} _ {k} \ سمت راست) _ {k}}$ ، با حد مجاز $\ mathbf {L$ . به راحتی قابل بررسی است که این $\ mathbf {L$ دارای خواص مورد نظر ، یعنی $\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^ {*}}$ و

$\ mathbf {L$ مثلث پایین با ورودی های مورب غیر منفی است: برای همه $ایکس$ و $ی$ ،

$\ displaystyle \ langle \ mathbf {A} x، y \ rangle = \ left \ langle \ lim \ mathbf {A} _ {k} x، y \ Right \ rangle = \ langle \ lim \ mathbf {L} _ { k} \ mathbf {L} _ {k} ^ {*} x، y \ rangle = \ langle \ mathbf {L} \ mathbf {L} ^ {*} x، y \ rangle \ ،.}$

از این رو، $\ displaystyle \ mathbf {A} = \ mathbf {L} \ mathbf {L} ^ {*}}$ . از آنجا که فضای بردار زیرین محدود است ، تمام توپولوژی های موجود در فضای اپراتورها معادل هستند. بنابراین ${\ نمایش صفحه \ سمت چپ (\ mathbf {L} _ {k} \ سمت راست) _ {k}}$ تمایل دارد

$\ mathbf {L$ به معنای هنجار ${\ نمایش صفحه \ سمت چپ (\ mathbf {L} _ {k} \ سمت راست) _ {k}}$ تمایل دارد $\ mathbf {L$ ورودی این به نوبه خود نشان می دهد که ، از هر یک $\ displaystyle \ mathbf {L} _ {k}}$ مثلث پایین با ورودی های مورب غیر منفی است ، $\ mathbf {L$ هم هست

اثبات تجزیه QR [ ویرایش ]

اجازه دهید $\ mathbf {A$ یک ماتریس نیمه قطعی مثبت هرمی باشد. سپس می توان آن را به عنوان محصولی از ماتریس ریشه مربع آن نوشت ، $\ displaystyle \ mathbf {A} = \ mathbf {B} \ mathbf {B} ^ {*}}$ . اکنون می توان تجزیه QR را نیز اعمال کرد $\ displaystyle \ mathbf {B} ^ {*}}$ ، منجر به $\ displaystyle \ mathbf {B} ^ {*} = \ mathbf {Q} \ mathbf {R}}$ ، جایی که $\ mathbf {Q$ واحد است و $\ mathbf {R$ مثلث فوقانی است درج تجزیه در بازده اصلی برابری

$\ displaystyle A = \ mathbf {B} \ mathbf {B} ^ {*} = (\ mathbf {QR}) ^ {*} \ mathbf {QR} = \ mathbf {R} ^ {*} \ mathbf {Q } ^ {*} \ mathbf {QR} = \ mathbf {R} ^ {*} \ mathbf {R}$ . تنظیمات

$\ displaystyle \ mathbf {L} = \ mathbf {R} ^ {*}$ اثبات را کامل می کند.

تعمیم [ ویرایش ]

فاکتورسازی Cholesky را می توان [با استناد به نیاز ] برای ماتریس (نه لزوما محدود) با ورودی اپراتور تعمیم داد . اجازه دهید

$\ {{\ mathcal {H}} _ {n} \}$ دنباله ای از فضاهای هیلبرت باشید . ماتریس اپراتور را در نظر بگیرید

$\ mathbf {A} = {\ آغاز {bmatrix} \ mathbf {A} _ {11} & \ mathbf {A _ {12} & \ mathbf {A} _ {13} & \؛ \\\ mathbf {A _ {12} ^ {*} & \ mathbf {A} _ {22} & \ mathbf {A} _ {23} & \؛ \\\ mathbf {A} _ {13} ^ {*} & \ mathbf {A} _ {23} ^ {*} & \ mathbf {A} _ {33} & \؛ \\\؛ & \؛ & \؛ & \ ddots \ end {bmatrix}$

اقدام به مبلغ مستقیم

$\ displaystyle {\ mathcal {H}} = \ bigoplus _ {n} {\ mathcal {H}} _ {n،$

جایی که هر کدام

$\ mathbf {A} _ {ij}: {\ mathcal {H}} _ {j} \ rightarrow {\ mathcal {H}} _ {i}$

یک اپراتور محدود است . اگر A مثبت باشد (semidefinite) به این معنا که برای همه k K محدود و برای هر

$\ displaystyle h \ in \ bigoplus _ {n = 1} ^ {k} {\ mathcal {H}} _ {k}،$

ما داریم $\ langle h، \ mathbf {A} h \ rangle \ geq 0$ ، سپس یک ماتریس اپراتور مثلثی L پایین وجود دارد به گونه ای که A = LL *. همچنین می توان ورودی های مورب L را مثبت دانست.

منبع

https://en.wikipedia.org/wiki/Cholesky_decomposition#

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی