در جبر خطی ، یک تجزیه و تحلیل QR ، همچنین به عنوان فاکتورسازی QR یا فاکتورسازی QU شناخته می شود ، تجزیه یک ماتریس A به یک محصول A  =  QR از یک ماتریس متعامد Q و یک ماتریس مثلثی R بالا است . تجزیه QR اغلب برای حل مسئله حداقل مربعات خطی مورد استفاده قرار می گیرد و پایه و اساس یک الگوریتم خاص مقدمه خاص ، الگوریتم QR است .

 

فهرست

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

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

هر واقعی ماتریس مربع ممکن است به عنوان تجزیه

A = QR ، \ ،

که در آن Q یک ماتریس متعامد است (ستون های آن بردارهای واحد متعامد به معنی هستند= I\ displaystyle Q ^ {\ Texff {T}} Q = QQ ^ {\ Texff {T}} = I) و R یک ماتریس مثلثی فوقانی است (از این رو نام ماتریس مثلثی راست نیز نامیده می شود). اگر است وارون ، سپس فاکتور منحصر به فرد است در صورت نیاز به عناصر مورب R مثبت باشد.

اگر در عوض A یک ماتریس مربع پیچیده باشد ، پس تجزیه A = QR وجود دارد که Q یک ماتریس واحد است (بنابراین\ displaystyle Q ^ {*} Q = QQ ^ {*} = I)

اگر است N مستقل خطی ستون، پس از آن اولین نفر ستون از Q فرم اساس orthonormal برای فضای ستون از . به طور کلی، برای اولین بار ک ستون از Q به صورت orthonormal برای فرم دهانه از اولین K ستون از برای هر 1 ≤  K  ≤  N . [1] این واقعیت که هر ستون K از تنها در اولین بستگی دارد ک ستون از Q مسئول شکل مثلثی  R است . [1]

ماتریس مستطیل شکل [ ویرایش ]

به طور کلی، ما می توانیم یک مجتمع عامل متر × N ماتریس ، با متر  ≥  N ، به عنوان محصول یک متر × متر ماتریس واحد Q و یک متر × N ماتریس بالا مثلثی R . از آنجا که سطرهای پایین ( m - n ) یک ماتریس مثلثی فوقانی m × n کاملاً از صفر تشکیل شده است ، اغلب برای تقسیم R یا هر دو R و Q مفید است :

\ displaystyle A = QR = Q {\ شروع {bmatrix} R_ {1} \\ 0 \ end {bmatrix} = {\ fill bmatrix} Q_ {1، Q_ {2} \ end {bmatrix}} { \ fill bmatrix} R_ {1} \\ 0 \ end {bmatrix}} = Q_ {1} R_ {1}،

که در آن R 1 یک IS N × N ماتریس بالا مثلثی، 0 است ( متر  -  N ) × N ماتریس صفر، Q 1 است متر × N ، Q 2 است متر × ( متر  -  N ) و Q 1 و Q 2 هر دو ستون های متعامد

گلوب و ون وام (1996 ، §5.2) پاسخ Q 1 R 1 فاکتور QR نازک از ؛ Trefethen و Bau این را عامل پایین تر QR می نامند . [1] اگر است کامل رتبه N و ما نیاز دارند که عناصر مورب R 1 مثبت سپس R 1 و Q 1 منحصر به فرد هستند، اما در کل Q 2 است. R 1 و سپس به عامل مثلثی بالای برابر است تجزیه Cholesky از * A (=  A T A اگر A واقعی باشد).

تجزیه QL ، RQ و LQ [ ویرایش ]

به طور مشابه ، ما می توانیم تجزیه QL ، RQ و LQ را تعریف کنیم که L یک ماتریس مثلثی پایین تر است.

محاسبه تجزیه QR [ ویرایش ]

روشهای مختلفی برای محاسبه در واقع تجزیه QR وجود دارد ، از جمله با استفاده از فرآیند گرم-اشمیت ، تحولات خانه دار یا چرخش گینز . هر کدام دارای چندین مزیت و مضرات هستند.

با استفاده از فرآیند گرم-اشمیت [ ویرایش ]

اطلاعات بیشتر: گرم-اشمیت stability ثبات عددی

فرایند Gram-Schmidt را که در ستونهای ماتریس مرتبه کامل ستون اعمال می شود ، در نظر بگیرید{\ displaystyle A = \ left [\ mathbf {a} _ {1}، \ ldots، \ mathbf {a} _ {n} \ Right]\ displaystyle \ langle \ mathbf {v}، \ mathbf {w} \ rangle = \ mathbf {v} ^ {\ textf T}} \ mathbf {w} (یا\ displaystyle \ langle \ mathbf {v}، \ mathbf {w} \ rangle = \ mathbf {v} ^ {*} \ mathbf {w} برای مورد پیچیده).

طرح را تعریف کنید :

\ displaystyle \ operatorname {proj} _ {\ mathbf {u}} \ mathbf {a} = {\ frac {\ left \ langle \ mathbf {u}، \ mathbf {a} \ Right \ rangle} {\ چپ \ langle \ mathbf {u}، \ mathbf {u} \ Right \ rangle}} {\ mathbf {u}}}

سپس:

\ displaystyle {\ شروع {تراز شده} \ mathbf {u} _ {1} & = \ mathbf {a} _ {1} ، & \ mathbf {e} _ {1} & = {\ mathbf {u} _ 1} \ over \ | \ mathbf {u} _ {1} \ |} \\\ mathbf {u} _ {2} & = \ mathbf {a} _ {2 - \ operatorname {proj} _ {\ mathbf {u} _ {1}} \، \ mathbf {a} _ {2}، & \ mathbf {e} _ {2} & = {\ mathbf {u} _ {2} \ over \ | \ mathbf {u _ {2} \ |} \\\ mathbf {u} _ {3} & = \ mathbf {a} _ {3} - \ operatorname {proj} _ {\ mathbf {u} _ {1}} \، \ mathbf {a} _ {3} - \ operatorname {proj} _ {\ mathbf {u} _ {2}} \، \ mathbf {a} _ {3}، & \ mathbf {e} _ {3} & = {\ mathbf {u} _ {3} \ over \ | \ mathbf {u} _ {3} \ |} \\ & \ vdots && \ vdots \\\ mathbf {u} _ {k} & = \ mathbf a _ {k} - \ sum _ {j = 1} ^ {k-1} \ operatorname {proj} _ {\ mathbf {u} _ {j}} \، \ mathbf {a} _ {k} ، & \ mathbf {e} _ {k} & = {\ mathbf {u} _ {k} \ over \ | \ mathbf {u} _ {k} \ |} \ end {تراز شده}}

اکنون می توانیم بیان کنیم\ mathbf {a} _iبر اساس مبنای ارتودنسی تازه محاسبه شده ما:

\ displaystyle {\ شروع {تراز شده} \ mathbf {a} _ {1} & = \ langle \ mathbf {e} _ {1}، \ mathbf {a} _ {1} \ rangle \ mathbf {e} _ { 1} \\\ mathbf {a} _ {2} & = langle \ mathbf {e} _ {1}، \ mathbf {a} _ {2} \ rangle \ mathbf {e} _ {1} + \ langle \ mathbf {e} _ {2}، \ mathbf {a} _ {2} \ rangle \ mathbf {e} _ {2} \\\ mathbf {a} _ {3} & = langle \ mathbf {e} _ {1} ، \ mathbf {a} _ {3} \ rangle \ mathbf {e} _ {1} + \ langle \ mathbf {e} _ {2}، \ mathbf {a} _ {3} \ rangle \ mathbf {e} _ {2} + \ langle \ mathbf {e} _ {3}، \ mathbf {a} _ {3} \ rangle \ mathbf {e} _ {3} \\ & \ vdots \\\ mathbf {a _ {k} & = \ sum _ {j = 1} ^ {k} \ langle \ mathbf {e} _ {j}، \ mathbf {a} _ {k} \ rangle \ mathbf {e} _ {j} \ end {تراز شده}}}

\ displaystyle \ left \ langle \ mathbf {e} _ {i}، \ mathbf {a} _ {i} \ Right \ rangle = \ left \ | \ mathbf {u} _ {i} \ Right \ |}. این را می توان به شکل ماتریس نوشت:

A = QR

جایی که:

{\ displaystyle Q = \ left [\ mathbf {e} _ {1}، \ ldots، \ mathbf {e} _ {n} \ Right]

و

\ displaystyle R = {\ fill {pmatrix} \ langle \ mathbf {e} _ {1}، \ mathbf {a} _ {1} \ rangle & \ langle \ mathbf {e} _ {1}، \ mathbf { a} _ {2} \ rangle & \ langle \ mathbf {e} _ {1}، \ mathbf {a} _ {3 \ rangle & \ ldots \\ 0 & langle \ mathbf {e} _ {2}، \ mathbf {a} _ {2} \ rangle & \ langle \ mathbf {e} _ {2}، \ mathbf {a} _ {3} \ rangle & \ ldots \\ 0 & 0 & \ langle \ mathbf {e} _ { 3} ، \ mathbf {a} _ {3} \ rangle & \ ldots \\\ vdots & \ vdots & \ vdots & \ ddots \ end {pmatrix}.

مثال [ ویرایش ]

در نظر بگیرید تجزیه

\ displaystyle A = {\ fill {pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ - 4 & 24 & -41 \ end {pmatrix}}.

به یاد بیاورید که یک ماتریس متعامد متعارف س دارایی داره

\ displaystyle Q ^ {\ textf {T}} \، Q = I.

سپس ، می توانیم محاسبه کنیم س با استفاده از گرم-اشمیت به شرح زیر است:

\ displaystyle {\ fill {تراز شده} U = {\ fill {pmatrix} \ mathbf {u} _ {1} & \ mathbf {u} _ {2} & \ mathbf {u} _ {3} \ end {pmatrix }} & = {\ fill {pmatrix} 12 & -69 & -58 / 5 \\ 6 & 158 & 6/5 \\ - 4 & 30 & -33 \ end {pmatrix}}؛ \\ Q = {\ fill pmatrix} {\ frac {\ mathbf {u} _ {1}} {\ | \ mathbf {u} _ {1} \ |}} & {\ frac {\ mathbf {u} _ {2}} {\ | \ mathbf {u} _ { 2} \ |}} & {\ frac {\ mathbf {u} _ {3}} {\ | \ mathbf {u} _ {3} \ |}} \ end {pmatrix} & = begin \ آغاز {pmatrix } 6/7 & -69 / 175 & -58 / 175 \\ 3/7 & 158/175 & 6/175 \\ - 2/7 & 6/35 & -33 / 35 \ end {pmatrix}}. \ end {تراز شده}}

بنابراین ، ما داریم

\ displaystyle {\ شروع {تراز شده} Q ^ {\ Texff {T}} A & = Q ^ {\ Texf {T}} Q \، R = R؛ \\ R & = Q ^ {\ tekstf T}} A = {\ fill pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & 35 \ end {pmatrix}}. \ end {تراز شده}}}

رابطه با تجزیه RQ [ ویرایش ]

تجزیه RQ یک ماتریس A را به محصول یک ماتریس مثلثی R بالایی (که به عنوان مثلث راست نیز معروف است) و یک ماتریس Q متعامد متعامد تبدیل می کند . تنها تفاوت در تجزیه QR ، ترتیب این ماتریس ها است.

تجزیه QR ارتودنسی ستون های گرم-اشمیت ستون های A است که از ستون اول شروع شده است.

تجزیه RQ ارتودنسی سازی گرم-اشمیت ردیف های A است ، از ردیف آخر شروع شده است.

مزایا و معایب [ ویرایش ]

روند گرام-اشمیت ذاتاً از نظر عددی بی ثبات است. در حالی که کاربرد پیش بینی ها دارای یک قیاس هندسی جذاب با ارتزونزاسیون است ، خود ارتودنسی شدن مستعد خطای عددی است. با این وجود یک مزیت مهم سهولت اجرای آن است که باعث می شود در صورت عدم دسترسی کتابخانه جبر خطی از پیش ساخته ، از الگوریتم مفیدی برای نمونه سازی استفاده شود.

استفاده از بازتاب های خانه دار [ ویرایش ]

بازتاب خانه دار برای تجزیه و تحلیل QR: هدف این است که یک تحول خطی پیدا کنید که بردار را تغییر می دهدایکس به یک بردار با همان طول که برابر است با خط e_ {1. ما می توانیم از یک طرح ریزی متعامد (گرم-اشمیت) استفاده کنیم اما اگر بردارها از نظر عددی ناپایدار باشند.ایکس وe_ {1نزدیک به متعامد هستند. در عوض ، انعکاس خانه دار از طریق خط نقطه ای (که برای گسسته کردن زاویه بین آنها انتخاب شده است) منعکس می شود{\ نمایشگر x}ایکس و {\ نمایشگر e_ {1}}e_ {1) حداکثر زاویه با این ترانسفر 45 درجه است.

سرپرست خانوار بازتاب (یا سرپرست خانوار تحول ) یک تغییر و تحول که طول می کشد یک بردار و آن را نشان دهنده در مورد برخی است هواپیما و یا ابرصفحه . ما می توانیم از این عملیات برای محاسبه فاکتور QR یک ماتریس m -by- n استفاده کنیمآبا m  ≥  n .

Q می تواند برای بازتاب یک بردار به گونه ای استفاده شود که همه مختصات اما یکی از بین بروند.

اجازه دهید \ mathbf {x یک واقعی خودسرانه متر بردار ستونی بعدی ازآ به طوری که \ | \ mathbf {x} \ | = | \ alpha |برای یک اسکالر α . اگر این الگوریتم با استفاده از حساسیت شناور-نقطه شناور پیاده سازی شود ، باید α علامت مخالف را به عنوان مختصات k -th از\ mathbf {x ، جایی که x_ {k}این است که به محور مختصات و پس از آن تمام پست های 0 در ماتریس ، بازدید کنندگان نهایی شکل مثلثی بالا، برای جلوگیری از از دست دادن اهمیت . در مورد پیچیده ، مجموعه

\ displaystyle \ alpha = -e ^ {i \ arg x_ {k}} \ | \ mathbf {x} \ |

( Stoer & Bulirsch 2002 ، p. 225) و جابجایی پیوند مزدوج را در ساخت و ساز Q در زیر جایگزین کنید

بعد ، کجا \ mathbf {e} _ {1}وکتور است (1 0… 0) T ، || · || است هنجار اقلیدسی ومنیک IS متر -by- متر ماتریس، مجموعه ای

\ displaystyle {\ شروع {تراز شده} \ mathbf {u} & = \ mathbf {x} - \ alpha \ mathbf {e} _ {1}، \\\ mathbf {v} & = {\ mathbf {u} \ over \ | \ mathbf {u} \ |}، \\ Q& = I-2 \ mathbf {v} \ mathbf {v} ^ {\ متنff {T}}. \ end {تراز شده}}}

یا اگر آ پیچیده است

\ displaystyle Q = I-2 \ mathbf {v} \ mathbf {v} ^ {*}.

{\ نمایشگر Q}سیک متر -by- متر سرپرست خانوار ماتریس و

\ displaystyle Q \ mathbf {x} = {\ fill {pmatrix} \ alpha & 0 & \ cdots & 0 \ end {pmatrix}} ^ {\ Texff {T}}. \،

این را می توان به تدریج تبدیل یک استفاده متر -by- N ماتریس به بالا مثلثی شکل. ابتدا ، A را با ماتریس Q 1 که در اولین ستون ماتریس برای x انتخاب می کنیم ضرب می کنیم . این منجر به یک ماتریس Q 1 A با صفرهای در ستون سمت چپ (به جز ردیف اول) می شود.

\ displaystyle Q_ {1} A = {\ fill bmatrix} \ alpha _ {1} & \ star & \ dots & \ star \\ 0 &&&&=* vdots && A '& \\ 0&&&& end / mat bmatrix}}

این می تواند برای A repeated تکرار شود ( با حذف ردیف اول و ستون اول از Q 1 A بدست می آید ) ، و در نتیجه یک ماتریس Householder Q ′ 2 حاصل می شود . توجه داشته باشید که Q ، 2 کوچکتر از Q 1 . از آنجا که ما می خواهیم آن را واقعا به در عمل Q 1 جای "ما نیاز به گسترش آن را به سمت چپ بالا، پر کردن یک 1 و یا به طور کلی:

\ displaystyle Q_ {k} = {\ fill pmatrix} I_ {k-1} & 0 \\ 0 & Q_ {k} '\ end {pmatrix}.

بعد از تی تکرار این روند ،\ displaystyle t = \ دقیقه (m-1 ، n)،

{\ displaystyle R = Q_ {t} \ cdots Q_ {2} Q_ {1} A

یک ماتریس مثلثی فوقانی است. بنابراین ، با

\ displaystyle Q = Q_ {1} ^ {\ Texff {T}} Q_ {2} ^ {\ Texff {T}} \ cdots Q_ {t} ^ {\ textf T}}،

A = QR تجزیه QR استآ.

این روش از ثبات عددی بیشتری نسبت به روش گرام-اشمیت در بالا برخوردار است.

در جدول زیر تعداد عملیات در مرحله k -th QR- تجزیه QR با تبدیل خانه دار آورده شده است ، با فرض یک ماتریس مربع با اندازه n .

عملتعداد عملیات در مرحله k -th
ضربات\ displaystyle 2 (n-k + 1) ^ {2}
موارد اضافی\ displaystyle (n-k + 1) ^ {2} + (n-k + 1) (nk) +2}
بخش1
ریشه دوم1

با جمع بندی این اعداد در مرحله n  - 1 (برای یک ماتریس مربع از اندازه n ) ، پیچیدگی الگوریتم (از نظر ضرب های نقطه شناور) توسط

\ displaystyle {\ frac {2} {3}} n ^ {3} + n ^ {2} + {\ frac {1} {3}} n-2 = O \ left (n ^ {3} \ Right .

مثال [ ویرایش ]

بگذارید تجزیه را محاسبه کنیم

\ displaystyle A = {\ fill {pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ - 4 & 24 & -41 \ end {pmatrix}}.

ابتدا باید بازتابی پیدا کنیم که اولین ستون ماتریس A ، وکتور را دگرگون کند\ displaystyle \ mathbf {a _ {1} = {\ fill {pmatrix} 12 & 6 & -4 \ end {pmatrix}} ^ {\ Texsf {T}}}، به \ displaystyle \ left \ | \ mathbf {a} _ {1} \ Right \ | \؛ \ mathbf {e} _ {1} = {\ fill pmatrix} 1 & 0 & 0 \ end {pmatrix}} ^ {\ متنf T}}.

اکنون،

\ mathbf {u} = \ mathbf {x} - \ alpha \ mathbf {e} _1،

و

\ displaystyle \ mathbf {v} = {\ mathbf {u} \ over \ | \ mathbf {u} \ |}.}

اینجا،

\ displaystyle \ alpha = 14 و\ displaystyle \ mathbf {x} = \ mathbf {a _ {1} = {\ fill {pmatrix} 12 & 6 & -4 \ end {pmatrix} ^ {\ Texff {T}}}

از این رو

\ displaystyle \ mathbf {u} = {\ fill {pmatrix} -2 & 6 & -4 \ end {pmatrix} ^ {\ Texff {T}} = {\ fill pmatrix 2 \ end {pmatrix}} {\ pmatrix} -1 & 3 & -2 \ end {pmatrix} ^ {\ textf T}}} و\ displaystyle \ mathbf {v} = {1 \ over {\ sqrt {14}}} {\ fill {pmatrix} -1 & 3 & -2 \ end {pmatrix} ^ {\ Texff {T}}}و بعد

\ displaystyle {\ شروع {تراز شده} Q_ {1} = {} & I- {2 \ {\ sqrt {14}} {\ sqrt {14}}} {\ آغاز {pmatrix} -1 \\ 3 \\ -2 \ end {pmatrix}} {\ fill {pmatrix} -1 & 3 & -2 \ end {pmatrix}} \\ = {} & I- {1 \ over 7 {\ fill pmatrix 1 & -3 & 2 \\ - 3 & 9 & -6 \\ 2 & -6 & 4 \ end {pmatrix}} \\ = {} & {\ fill pmatrix} 6/7 & 3/7 & -2 / 7 \\ 3/7 & -2 / 7 & 6/7 \\ - 2 / 7 و 6/7 و 3/7 \ پایان \ {pmatrix}}.

اکنون مشاهده کنید:

\ displaystyle Q_ {1} A = {\ fill pmatrix} 14 & 21 & -14 \\ 0 & -49 & -14 \\ 0 & 168 & -77 \ end {pmatrix}}،}

بنابراین ما در حال حاضر تقریبا یک ماتریس مثلثی داریم. فقط باید ورودی (3 و 2) را صفر کنیم.

(1 ، 1) جزئی را بگیرید و دوباره این روند را روی آن اعمال کنید

\ displaystyle A '= M_ {11} = {\ fill pmatrix 49 -49 & -14 \\ 168 & -77 \ end {pmatrix}.}

با همان روشی که در بالا ذکر شد ، ماتریس تحول Householder را بدست می آوریم

\ displaystyle Q_ {2} = {\ fill {pmatrix} 1 & 0 & 0 \\ 0 & -7 / 25 & 24/25 \\ 0 & 24/25 & 7/25 \ end pmatrix}}

پس از انجام یک مبلغ مستقیم با 1 تا اطمینان حاصل کنید که مرحله بعدی روند صحیح کار می کند.

اکنون ، ما می یابیم

\ displaystyle Q = Q_ {1} ^ {\ Texff {T}} Q_ {2} ^ {\ Texff {T}} = {\ fill pmatrix} 6/7 & -69 / 175 & 58/175 \\ 3/7 & 158 / 175 & -6 / 175 \\ - 2/7 & 6/35 & 33/35 \ end {pmatrix}}

یا به چهار رقم اعشاری ،

\ displaystyle {\ fill {تراز شده} Q & = Q_ {1} ^ {\ Texff {T}} Q_ {2} ^ {\ Texff {T}} = {\ fill pmatrix 0.8571 & -0.3943 & 0.3314 \ \ 0.4286 & 0.9029 & -0.0343 \\ - 0.2857 & 0.1714 & 0.9429 \ end {pmatrix} \\ R & = Q_ {2} Q_ {1} A = Q ^ {\ Texff {T}} A = {\ pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \ end {pmatrix}}. \ end {تراز وسط}}

ماتریس Q بصورت متعامد و R مثلثی فوقانی است ، بنابراین A = QR تجزیه QR مورد نیاز است.

منبع

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