변형 된 Gram-Schmidt가 고전적인 것보다 더 안정적인 이유에 대한 직관적 인 설명?
이것은 오래된 질문 일 수 있으며 아래에서 언급 할 관련 게시물이 확실히 있습니다. 하지만 아직 명확한 답이없는 것 같습니다. 질문은 매트릭스의 QR 분해를 수행하기 위해 수정 된 그램-슈미트 (MGS) 프로세스가 왜 수정 된 이유를 설명하는 직관적 인 방법이 있는가입니다.$A\in\mathbb{C} ^{m\times n}$ 제공 $Q$고전적인 그람-슈미트 (CGS) 과정에서 나온 것보다 "더 직교하는"행렬? "직관적"으로 설명이 MGS와 CGS의 절차 적 차이와 투명하게 관련 될 수 있기를 바랍니다.
Trefethen의 Numerical Linear Algebra 에서 CGS와 MGS의 차이점은 다음과 같습니다.
에서 $j$두 번째 단계, 두 GS 프로세스 모두 $q_j$ 같이 $$ q_j=\frac{P_j a_j }{\|| P_j a_j \|| } $$ CGS의 경우 $$ P_j=I-Q_{j-1}Q_{j-1}^* $$ 하지만 MGS의 경우 $$ P_j=(I-q_{j-1}q_{j-1}^* )...(I-q_2q_2^* )(I-q_1q_1^* ) $$
Trefethen은이 절차상의 차이가 MGS의 수치 안정성을 향상시키는 이유를 논의하지 않습니다.
@AlgebraicPavel은 여기 직교성 요인에 대한 양적 한계를 지정했습니다 .$\||I-Q^* Q\||\leq O(\epsilon \kappa(A))$ MGS의 경우 $\||I-Q^* Q\||\leq O(\epsilon \kappa^2(A))$CGS를 위해. 이 결과는 충분히 정량적입니다. 그러나 위에서 언급했듯이 이것이 어떻게 나오는지에 대한보다 직관적 인 추론을 원합니다.
@Ian은 여기에서 말했습니다.
"(k + 1) 번째 벡터의 첫 번째 k 벡터에 대한 투영을 빼는 고전적인 Gram-Schmidt는 특히 높은 차원에서 매우 불안정합니다. 왜냐하면 기본적으로 새 벡터가 입력에 직교하는지 확인하기 때문입니다. 문제의 벡터이지만 프로세스가 끝날 때 얻은 벡터가 서로 직교하는지 확인하지 못했습니다. 거의 동일한 수를 뺄 수 있다는 사실과 결합하면 나쁜 상황이 발생합니다. "
이것은 CGS의 문제에 대한 직관적이고 질적 인 설명처럼 들립니다. 그러나 세부 사항으로 들어가면 이러한 추론 라인에 대해 편안하지 않습니다. 특히, "새로운 벡터가 문제의 입력 벡터에 직교한다"는 말은 CGS가하는 일과 일치하지 않는 것 같습니다. CGS와 MGS 모두에 대해 새 벡터 ($a_j$)는 기존에 직교하도록하기 위해 뺍니다. $q_i, i=1,...,j-1$. 이것을 부르는 것이 적절하지 않을 수 있습니다$q_i$ "입력 벡터"이며 이것은 MGS와 CGS의 주요 절차상의 차이점을 다루지 않습니다.
에서 이 포스트는$4\times 3$Lauchli 행렬은 MGS와 CGS 간의 다른 결과를 데모하는 예제로 사용됩니다. 질문에 대한 직관적 인 설명도 아직 없지만이 Lauchli 예제의 결과는$q_3^{CGS}$ 직교하지 않음 $q_2^{CGS}$ 왜냐하면 $r_{23}^{CGS}$100 %의 상대 오차로 잘못 계산됩니다. 그러나 MGS 절차가이 문제를 크게 완화 할 수있는 이유를 알 수 없습니다.
의견을 보내 주셔서 대단히 감사합니다.
답변
CGS와 MGS 모두에서 기둥에 대한 투영을 빼는 직교 화 단계 $Q$이미 계산 된 것은 유한 정밀도 산술로 인해 오류를 발생시킵니다. 각 열$\mathbf{q}_i$ 의 $Q$ 따라서 이전에 계산 된 열 방향으로 약간의 오류 구성 요소가 있습니다. $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$. 열 번호를 늘리면 오류가 누적됩니다.$i$, 이는 두 알고리즘의 고유 한 약점입니다.
CGS에서 기둥의 직교 화 $n$ 칼럼에 대하여 $\mathbf{q}_{i}$ ($i<n$)의 원래 열을 투영하여 수행됩니다. $A$ (이것을 불러 $\mathbf{a}_n$)에 $\mathbf{q}_{i}$ 그리고 빼기. $$ \begin{split} \mathbf{p}_{n} &\equiv \mathbf{a_n} - \sum_{i=1}^{n-1}(\mathbf{q_i^T}\cdot \mathbf{a_n})\mathbf{q_i} \\ \mathbf{q}_{n} &= \frac{\mathbf{p}_{n}}{\|\mathbf{p}_{n}\|} \end{split} $$ 반면 MGS에서는 각 구성 요소가 $\mathbf{q}_i$ 열 오른쪽의 나머지 열에서 즉시 뺍니다. $i$ 즉시 $\mathbf{q}_i$계산됩니다. 따라서 기둥의 직교 화$n$ 에 맞서 $\mathbf{q}_{i}$ 투영에 의해 수행되지 않습니다 $\mathbf{q}_{i}$ 의 원래 열에 대해 $A$ CGS에서와 같이, 오히려 해당 열에서 빼서 얻은 벡터에 대해 $A$ span ($\mathbf{q}_1….\mathbf{q}_{i-1}$). 이것은 오류 구성 요소 때문에 중요합니다.$\mathbf{q}_i$, 어느 범위 $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$.
보다 정확하게는 MGS에서 컬럼의 직교 화 $n$ 에 맞서 $\mathbf{q}_{i}$ 구성 요소를 빼서 수행됩니다. $\mathbf{q}_{i}$ 벡터에서 $\mathbf{v}_n^{i-1}$, 어디 $\mathbf{v}_n^0\equiv \mathbf{a}_n$ 과 $\mathbf{v}_n^i$ ($0<i<n$)는 다음과 같이 정의됩니다. $$ \begin{split} \mathbf{v}_n^{i}&\equiv \mathbf{v}_n^{i-1} -(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})\mathbf{q}_{i}, \\ \mathbf{q}_n &= \frac{\mathbf{v}_n^{n-1}}{\|\mathbf{v}_n^{n-1}\|} \end{split} $$ 위의 식에서 괄호 안의 투영 계수의 차이를 확인하십시오. $(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})$, CGS에 해당하는 것, ($\mathbf{q_i^T}\cdot \mathbf{a_n}$). 벡터$\mathbf{q}_i$ span ($\mathbf{q}_1….\mathbf{q}_{i-1}$)이 투영 계수에 오류가 발생합니다. 반면에 벡터$\mathbf{a}_n$ 일반적으로 span ($\mathbf{q}_1….\mathbf{q}_{i-1}$), 벡터 $\mathbf{v}_n^{i-1}$ span ($\mathbf{q}_1….\mathbf{q}_{i-1}$) 컴퓨팅에서 $\mathbf{v}_n^{i-1}$ 그 구성 요소 $\mathbf{a}_n$ 스팬 ($\mathbf{q}_1….\mathbf{q}_{i-1}$)이 이미 제거되었습니다. 결과적으로이 곱셈 계수의 오류는 다음 사이의 불완전한 직교성으로 인한 것입니다.$\mathbf{q}_i$ 과 $\{\mathbf{q}_1...\mathbf{q}_{i-1}\}$ CGS보다 MGS에서 훨씬 작습니다.
이 투영 계수의 오류가 훨씬 작기 때문에 MGS는 CGS보다 각 감산 단계에서 직교 화 오류를 덜 발생시킵니다.