Orthogonalisation de Gram-Schmidt

L'outil affiche trois colonnes espacées de 10⁻⁸ et la réponse du Gram-Schmidt classique pour elles. Exécutez l'algorithme à la main, trouvez l'unique arrondi qui lui coûte trente degrés, puis indiquez jusqu'où chaque version peut être poussée avant de cesser d'être utile.

Ouvrez ce problème dans l'outil

1. Chaque colonne est le vecteur (1, 0, 0, 0) avec un seul ε glissé dans un emplacement différent. AᵀA est la matrice 3 × 3 remplie de un, plus ε²I. Ses valeurs propres sont 3 + ε² une fois et ε² deux fois. Les valeurs singulières sont donc √(3 + ε²) et ε, et le conditionnement est exact plutôt qu'estimé. La première ligne du tableau affiche 1,7321 × 10⁸.

   $$A=\left(\begin{array}{ccc}1& 1& 1\\ & & \\ \epsilon & 0& 0\\ & & \\ 0& \epsilon & 0\\ & & \\ 0& 0& \epsilon \end{array}\right),\epsilon =10^{-8},\kappa (A)=\frac{\sqrt{3+{\epsilon }^2}}{\epsilon }=1.7321\times 10^8$$

2. ‖a₁‖² vaut 1 + ε², et ε² vaut 10⁻¹⁶. Un double stocke 1, et le nombre suivant qu'il peut représenter se trouve 2,2204 × 10⁻¹⁶ plus loin. Tout ce qui est inférieur à la moitié de cet écart, soit 1,1102 × 10⁻¹⁶, disparaît lorsqu'on l'ajoute à 1. Dix puissance moins seize se situe en dessous. La racine carrée vaut 1. Diviser par celle-ci ne change rien, et q₁ ressort comme la colonne elle-même, avec le ε² rayé des registres. Chaque autre arrondi dans ce problème coûte une unité sur la dernière décimale. Celui-ci coûte trente degrés.

   $$\Vert a_1{\Vert }^2=1+{\epsilon }^2=1+10^{-16},10^{-16}<1.1102\times 10^{-16}⟹\mathrm{fl}(1+{\epsilon }^2)=1,q_1=a_1$$

3. Passons à la colonne 2. Les deux versions s'accordent ici puisqu'il n'y a qu'un seul vecteur derrière. Le coefficient de projection est q₁ᵀa₂ = 1. Soustraire cette valeur laisse (0, −ε, ε, 0), dont la longueur est ε√2 = 1,4142 × 10⁻⁸. La colonne 2 est arrivée avec une longueur de 1 pour autant qu'un double puisse en juger, et tout sauf 1,4142 × 10⁻⁸ était déjà couvert par q₁.

   $$r_{12}=q_1^{\mathsf{T}}{a}_2=1,v_2=a_2-q_1=(0,-\epsilon ,\epsilon ,0{)}^{\mathsf{T}},\Vert v_2\Vert =\epsilon \sqrt{2}=1.4142\times 10^{-8}$$

4. Colonne 3, version classique. Le coefficient sur q₁ est encore 1. Le coefficient sur q₂ est q₂ᵀa₃. Comme q₂ vit entièrement dans les positions 2 et 3 tandis que a₃ garde son ε dans la position 4, ce produit scalaire vaut 0. C'est ce qu'indique la ligne Ce que q₂ retire à la colonne 3. Soustraire q₁ seul laisse (0, −ε, 0, ε), de longueur ε√2 là encore. La ligne Ce qu'il reste de la colonne 3 affiche donc également 1,4142 × 10⁻⁸.

   $$r_{13}=q_1^{\mathsf{T}}{a}_3=1,r_{23}=q_2^{\mathsf{T}}{a}_3=0,v_3=a_3-q_1=(0,-\epsilon ,0,\epsilon {)}^{\mathsf{T}},q_3=\frac{1}{\sqrt{2}}(0,-1,0,1{)}^{\mathsf{T}}$$

5. Les vecteurs q₂ et q₃ ont tous deux été construits en retirant q₁ d'une colonne qui partage son 1 initial. Ils portent donc tous les deux −1/√2 dans la position 2 et n'ont rien d'autre en commun. Leur produit scalaire est un demi. L'outil imprime 0,5000 et 60,00°, et la valeur qu'il stocke est 0,4999999999999999, à une unité près du demi donné par l'algèbre, car ±1/√2 n'est pas une fraction binaire. C'est la taille d'erreur dont cette arithmétique est capable. Ce ne sont pas les trente degrés. La ligne de perte classique indique 0,7071, ce qui correspond à √(2 × 0,5²) : le même demi compté une fois dans chaque coin de QᵀQ.

   $$q_2^{\mathsf{T}}{q}_3=\frac{1}{2}[(-1)(-1)+(1)(0)]=\frac{1}{2},\arccos \frac{1}{2}=60^{\circ },\sqrt{2\cdot 0.5^2}=0.7071$$

6. La version modifiée, sur la même colonne. Une fois la part de q₁ retirée, le reste est (0, −ε, 0, ε), et cette version mesure par rapport à ce reste plutôt qu'à a₃. Le produit scalaire avec q₂ donne ε/√2 = 7,0711 × 10⁻⁹, et non zéro. Retirez cela et ce qui reste est (0, −ε/2, −ε/2, ε), de longueur ε√(3/2) = 1,2247 × 10⁻⁸. q₂ᵀq₃ sort à 1,1102 × 10⁻¹⁶ au lieu d'un demi. La ligne de perte modifiée affiche 1,1547 × 10⁻⁸. Tout ce qui y reste est ce que q₁ n'a pas pu enlever : la soustraction laisse −ε² couché le long de q₁, et diviser par un reste long de seulement ε√2 retransforme cela en ε/√2.

   $$r_{23}=q_2^{\mathsf{T}}{v}_3=\frac{\epsilon }{\sqrt{2}}=7.0711\times 10^{-9},v_3\mapsto (0,-\frac{\epsilon }{2},-\frac{\epsilon }{2},\epsilon {)}^{\mathsf{T}},\Vert v_3\Vert =\epsilon \sqrt{\frac{3}{2}}=1.2247\times 10^{-8},q_2^{\mathsf{T}}{q}_3=0$$

7. Le même argument vaut pour chaque nombre de colonnes proposé par l'outil. Le Gram-Schmidt classique construit chaque q ultérieur en retirant q₁ d'une colonne qui partage son 1 initial. Chaque paire entre eux ressort donc à 60° : (n − 1)(n − 2)/2 paires, avec une perte d'orthogonalité égale à la racine carrée de la moitié de ce compte. Avec deux colonnes, il n'y a pas de telles paires. Ce qui reste est l'inclinaison de taille ε que les deux versions partagent.

   $$\begin{array}{rrrrr}n& \kappa (A)& \#\{60^{\circ }\}& \Vert Q_C^{\mathsf{T}}{Q}_C-I{\Vert }_F& \Vert Q_M^{\mathsf{T}}{Q}_M-I{\Vert }_F\\ & & & & \\ 2& 1.4142\times 10^8& 0& 1.0000\times 10^{-8}& 1.0000\times 10^{-8}\\ & & & & \\ 3& 1.7321\times 10^8& 1& 0.7071& 1.1547\times 10^{-8}\\ & & & & \\ 4& 2.0000\times 10^8& 3& 1.2247& 1.2247\times 10^{-8}\\ & & & & \\ 5& 2.2361\times 10^8& 6& 1.7321& 1.2649\times 10^{-8}\end{array}$$

8. La ligne ajustée du mode classique atteint une perte de 1 à κ = 2,35 × 10⁸, ce qui explique pourquoi la courbe classique est déjà plate à l'extrémité droite du panneau. Le mode modifié obtient une borne mesurée plutôt qu'extrapolée. Sa propre courbe s'infléchit au-delà de 10⁻⁸ et une ligne ajustée prolongée si loin serait réfutée par le panneau en dessous. Sur les 724 points du balayage, sa perte n'a jamais dépassé 1,25 epsilon machine fois κ, et cette borne n'atteint 1 qu'à κ = 3,60 × 10¹⁵. L'inverse de l'epsilon machine est 4,50 × 10¹⁵.

   $$\begin{array}{rcl}{\log }_{10}\kappa =\frac{16.5755}{1.9801}& =& 8.3710⟹\kappa =2.35\times 10^8\\ & & \\ 1.25\cdot (2.2204\times 10^{-16})\kappa & =& 1⟹\kappa =3.60\times 10^{15}\\ & & \\ (2.2204\times 10^{-16}{)}^{-1}& =& 4.50\times 10^{15}\end{array}$$