تحويل رب الأسرة

تتمتع مصفوفة هاوسهولدر بالخصائص التالية:

• إنه هيرميتي :${\textstyle P=P^{*}}$،
• إنها وحدة واحدة :${\textstyle P^{-1}=P^{*}}$(عبر صيغة شيرمان-موريسون )،
• لذا فهو لا إرادي :${\textstyle P=P^{-1}}$.
• تحتوي مصفوفة هاوسهولدر على قيم ذاتية${\textstyle \pm 1}$ولرؤية ذلك، لاحظ أنه إذا${\textstyle {\vec {x}}}$متعامد مع المتجه${\textstyle {\vec {v}}}$والذي استُخدم لإنشاء العاكس، ثم$//$، أي،${\textstyle 1}$هي قيمة ذاتية للتعددية${\textstyle n-1}$، نظراً لوجود${\textstyle n-1}$متجهات مستقلة متعامدة مع${\textstyle {\vec {v}}}$لاحظ أيضًا$$$(منذ${\displaystyle {\vec {v}}}$(وهو بحكم التعريف متجه وحدة)، وبالتالي${\textstyle -1}$هي قيمة ذاتية ذات تعددية${\textstyle 1}$.
• محدد عاكس هاوسهولدر هو${\textstyle -1}$بما أن محدد المصفوفة هو حاصل ضرب قيمها الذاتية، وفي هذه الحالة إحداها هي${\textstyle -1}$أما الباقي فهو${\textstyle 1}$(كما في النقطة السابقة)، أو عبر مبرهنة محدد المصفوفة .

لنفترض عملية تطبيع متجه${\displaystyle {\vec {v}}}$يحتوي على${\displaystyle 1}$في كل مدخل،

${\displaystyle {\vec {v}}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\1\end{bmatrix}}.}$

ثم مصفوفة هاوسهولدر المقابلة للمتجه${\displaystyle v}$يكون

${\displaystyle P_{v}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-2\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\end{bmatrix}}\right)}$

${\displaystyle \quad ={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-{\begin{bmatrix}1\\1\end{bmatrix}}{\begin{bmatrix}1&1\end{bmatrix}}}$

${\displaystyle \quad ={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-{\begin{bmatrix}1&1\\1&1\end{bmatrix}}}$

${\displaystyle \quad ={\begin{bmatrix}0&-1\\-1&0\end{bmatrix}}.}$

لاحظ أنه إذا كان لدينا متجه آخر${\displaystyle {\vec {q}}}$يمثل إحداثية في المستوى ثنائي الأبعاد

${\displaystyle {\vec {q}}={\begin{bmatrix}x\\y\end{bmatrix}},}$

في هذه الحالة${\displaystyle P_{v}}$يقلب وينفي${\displaystyle x}$و${\displaystyle y}$إحداثيات، بمعنى آخر لدينا

${\displaystyle P_{v}{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}-y\\-x\end{bmatrix}},}$

وهذا يتوافق مع عكس المتجه عبر الخط${\displaystyle y=-x}$، وهو متجهنا الأصلي${\displaystyle {\vec {v}}}$وهذا طبيعي أيضاً.

يمكن استخدام تحويلات هاوسهولدر لحساب تحليل QR . لنفترض مصفوفة مربعة تم تحويلها إلى مصفوفة مثلثية علوية حتى العمود${\displaystyle i-1}$إذن، هدفنا هو بناء مصفوفات هاوسهولدر التي تؤثر على المصفوفات الفرعية الرئيسية لتلك المصفوفة، والتي تأخذ الشكل التالي:

${\displaystyle A^{(i)}={\begin{bmatrix}a_{11}&a_{12}&\cdots &&&a_{1n}\\0&a_{22}&\cdots &&&a_{1n}\\\vdots &&\ddots &&&\vdots \\0&\cdots &0&x_{1}=a_{ii}&\cdots &a_{in}\\0&\cdots &0&\vdots &&\vdots \\0&\cdots &0&x_{n+1-i}=a_{ni}&\cdots &a_{nn}\end{bmatrix}}}$

المصفوفة${\displaystyle A^{(i)}}$له شكل الكتلة

${\displaystyle A^{(i)}={\begin{bmatrix}T_{i-1}^{U}&*\\0&P_{v}\end{bmatrix}}}$.

لاحظ أن${\displaystyle A^{(n)}}$هي المصفوفة${\displaystyle R}$في${\displaystyle Q\,R}$التفكيك. هنا المصفوفة الفرعية${\displaystyle T_{i-1}^{U}}$هي مصفوفة مثلثية علوية مربعة من الرتبة i-1 × i-1، و0 تمثل مصفوفة صفرية من الرتبة n-i+1 × n-i+1، و* تمثل مصفوفة من الرتبة n-i+1 × n-i+1، و${\displaystyle P_{v}}$يمثل مصفوفة من الرتبة n-i+1 × n-i+1، والتي يجب تحويلها إلى مصفوفة مثلثية علوية من خلال العمل في فضاءها الجزئي دون تغيير شكل المصفوفة الكتلية الموضح أعلاه.${\displaystyle A^{(i)}}$.

لو${\displaystyle x_{1}=a_{ii}}$يساوي صفرًا ويوجد عنصر غير صفري${\displaystyle a_{ji}}$إذا كان j>i، فيمكن تبديل الصفين i و j عن طريق الضرب المسبق بمصفوفة تبديل الصفوف، وهي مصفوفة أحادية.${\displaystyle a_{ji}=0}$لكل j>=i، انتقل إلى العمود التالي.

لو${\displaystyle x_{1}=a_{ii}}$هو عدد مركب غير حقيقي معطى بواسطة${\displaystyle x_{1}=r_{1}e^{i\phi _{1}}}$لريال مدريد${\displaystyle r_{1}{\text{,}}\,\phi _{1}}$إذاً، يمكن ضرب هذه المصفوفة من اليسار بالمصفوفة القطرية الوحدوية U مع${\displaystyle U_{ii}=e^{-i\phi _{1}}}$وباستخدام 1 للعناصر القطرية الأخرى، وذلك لإنشاء العنصر الجديد${\displaystyle x_{1}}$عدد حقيقي غير صفري مع الحفاظ على شكل الكتلة. وهذا يضمن أن${\displaystyle \langle \mathbf {x} ,{\vec {e}}_{1}\rangle \,=\,\langle {\vec {e}}_{1},\mathbf {x} \rangle \,=\,x_{1}}$. هنا${\displaystyle {\vec {e}}_{1}}$هو متجه ذو أبعاد n، يحتوي على 1 في الموضع i و0 في باقي المواضع. (لاحظ أننا أثبتنا سابقًا أن تحويلات هاوسهولدر هي مصفوفات وحدوية، وبما أن ضرب المصفوفات الوحدوية هو في حد ذاته مصفوفة وحدوية، فإن هذا يعطينا المصفوفة الوحدوية لتحليل QR).

يترك${\displaystyle \mathbf {e} _{1}{\text{,}}\,\mathbf {e} _{2}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}}$لتكن متجهات الأساس للمصفوفات ذات الأبعاد n${\displaystyle A^{(i)}}$ودع${\displaystyle {\vec {e}}_{1}{\text{,}}\,{\vec {e}}_{2}{\text{,}}\,{\text{...}}{\text{,}}\,{\vec {e}}_{n-i+1}}$لتكن متجهات الأساس${\displaystyle \mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}}$، على التوالى.

إذا استطعنا أن نجد${\displaystyle {\vec {v}}}$لهذا السبب. $${\displaystyle P_{v}{\vec {x}}=\alpha {\vec {e}}_{1}}$$ يمكننا تمديد المثلث العلوي بعمود واحد. المتجه${\displaystyle \mathbf {v} }$يجب أن يكون في الفضاء الجزئي الممتد بواسطة المتجهات${\displaystyle \{\mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}\}}$ذلك المتجه${\displaystyle \mathbf {x} }$موجود. مع${\displaystyle x_{1}}$في الواقع، سيتضح ذلك.${\displaystyle \alpha }$وهو حقيقي أيضاً. بالتفكير الهندسي، نبحث عن مستوى بحيث ينعكس حوله متجه الأساس مباشرةً. بعبارة أخرى،

${\displaystyle {\vec {x}}-2\langle {\vec {x}},{\vec {v}}\rangle {\vec {v}}=\alpha {\vec {e}}_{1}}$

1

لبعض الثوابت${\displaystyle \alpha }$لكن لكي يحدث هذا، يجب أن يكون لدينا $${\displaystyle {\vec {v}}\propto {\vec {x}}-\alpha {\vec {e}}_{1}{\text{.}}}$$ ومنذ ذلك الحين${\displaystyle {\vec {v}}}$إذا كان متجه وحدة، فهذا يعني أنه يجب أن يكون لدينا

${\displaystyle {\vec {v}}=\pm {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}}$

2

سنجد أن هناك قيمتين محتملتين لـ${\displaystyle \alpha }$تلك القيمة التي تجعل${\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}$الأكبر هو الذي ينبغي استخدامه لتحقيق أعلى دقة.

الآن، إذا طبقنا المعادلة ( 2 ) مرة أخرى في المعادلة ( 1 )، فسنحصل على $${\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}=2\left\langle {\vec {x}},{\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}\right\rangle {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}}$$ أو بعبارة أخرى، من خلال مقارنة القيم العددية أمام المتجه${\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}}$يجب أن يكون لدينا $${\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}^{2}=2\langle {\vec {x}},{\vec {x}}-\alpha e_{1}\rangle {\text{.}}}$$ لو${\displaystyle x_{1}}$إذا كان حقيقيًا، فإن ألفا يكون حقيقيًا أيضًا ويتم الحصول عليه من المعادلة $${\displaystyle \|{\vec {x}}\|_{2}^{2}-2\alpha x_{1}+\alpha ^{2}=2(\|{\vec {x}}\|_{2}^{2}-\alpha x_{1})}$$ وهذا يعني $${\displaystyle \alpha =\pm \|{\vec {x}}\|_{2}}$$ لو${\displaystyle x_{1}}$ليس حقيقياً، إذن${\displaystyle \alpha }$وهي أيضاً ليست حقيقية ويتم الحصول عليها من المعادلة $${\displaystyle \|{\vec {x}}\|_{2}^{2}-\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1}+|\alpha |^{2}\,=\,2(\|{\vec {x}}\|_{2}^{2}-\alpha ^{*}\,x_{1})}$$ أو بعبارة أخرى، $${\displaystyle |\alpha |^{2}\,=\,\|{\vec {x}}\|_{2}^{2}+(\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1})}$$ الحد الموجود بين قوسين هو عدد تخيلي بحت، وتتطلب هذه المعادلة أن ${\displaystyle |\alpha |=\|{\vec {x}}\|_{2}}$وذلك${\displaystyle \arg(\alpha )\,=\,\arg(x_{1})}$ضمن مضاعفات${\displaystyle \pi }$.

بهذا يكتمل البناء؛ ومع ذلك، عمليًا، نريد تجنب الإلغاء الكارثي في ​​المعادلة ( 2 ). وللقيام بذلك بشكل حقيقي${\displaystyle x_{1}}$نختار ^{[ 5 ]} إشارة${\displaystyle \alpha }$مثل $${\displaystyle \alpha =-\operatorname {sgn}(\mathrm {Re} (x_{1}))\|{\vec {x}}\|_{2}}$$ وبالنسبة للتعقيد${\displaystyle x_{1}}$نختار اللافتة لـ${\displaystyle \alpha }$مثل${\displaystyle \alpha =-e^{i\,\arg(x_{1})}\,\|x\|_{2}}$، أين${\displaystyle i}$هو الجذر التربيعي لـ${\displaystyle -1}$وهذا يتوافق مع المعادلة المذكورة للتو لـ${\displaystyle \alpha }$متى${\displaystyle x_{1}}$هذا حقيقي. هذه الخيارات للعلامات تجعل${\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}$الأكبر. عندما${\displaystyle |x_{1}|\ll \|x\|_{2}}$لا فرق يُذكر في اختيار أي علامة.

يمكن تطبيق تحويلات هاوسهولدر بالمثل على مصفوفة معقدة مستطيلة غير مربعة. وتختلف عمليات التفكيك نوعًا ما.

في هذا المثال، أيضًا من Burden و Faires، ^{[ 10 ]} يتم تحويل المصفوفة المعطاة إلى المصفوفة ثلاثية الأقطار المماثلة A3 _{باستخدام} طريقة Householder.

${\displaystyle \mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},}$

باتباع هذه الخطوات في طريقة رب الأسرة، نحصل على:

مصفوفة هاوسهولدر الأولى:

${\displaystyle {\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}}$

مستخدم${\textstyle A_{2}}$لتشكيل

${\displaystyle {\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}}$

كما نرى، فإن النتيجة النهائية هي مصفوفة متناظرة ثلاثية الأقطار تشبه المصفوفة الأصلية. وتنتهي العملية بعد خطوتين.

بما أن المصفوفات الوحدوية مفيدة في الحوسبة الكمومية ، وتحويلات هاوسهولدر وحدوية، فإنها تُعدّ بالغة الأهمية في هذا المجال. ومن أبرز الخوارزميات التي تُستخدم فيها هذه المصفوفات خوارزمية غروفر، حيث نسعى لإيجاد تمثيل لدالة أوراكل، والتي تُمثّل بدورها بتحويل هاوسهولدر.

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}}$

(هنا الـ${\displaystyle |x\rangle }$يُعد جزءًا من تدوين برا-كيت وهو مماثل لـ${\displaystyle {\vec {x}}}$والتي كنا نستخدمها سابقاً)

يتم ذلك عبر خوارزمية تتكرر عبر دالة أوراكل${\displaystyle U_{\omega }}$ومشغل آخر${\displaystyle U_{s}}$يُعرف باسم عامل انتشار غروفر، ويُعرَّف بواسطة

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$ و${\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}$.