Mathematical Engineering - Matematica Numerica

Exercise 07

Divided by topic

MATEMATICA NUMERICA A.A. 2018 - 2019 Ingegneria Matematica Prof. A. Quarteroni Prof. A. Manzoni, Dr. I. Fumagalli Esercitazione 7 Sistemi sovradeterminati e Metodi iterativi per sistemi lineari (1) Esercizio 1 Sia data la seguente matrice che possiede rango pieno per ogni >0 A =2 41 1 0 03 5; e i vettorix ex= [1 ;1]T eb= Ax ex. Vogliamo calcolare x, la soluzione del seguente problema ai minimi quadratikAxbk2 2= min y2R2k Aybk2 2; benché sappiamo che la soluzione esatta di tale problema è propriox=x ex. a)Per= 10 i ; i= 1;2;3;4calcolarex=x 1risolvendo il sistema delle equazioni normali ovvero AT Ax 1= AT b: Per ogni valore di, calcolare l'errorekx 1 x exk 2e visualizzarlo in funzione di su un graco in scala logaritmica, insieme all'andamento del numero di condizionamentoK 2(AT A). b)Per gli stessi valori didel punto precedente, calcolarex=x 2sfruttando la fattorizzazione~ Q~ Rridotta diA, ovvero applicando la relazione, x2=~ R 1 ~ QT b: Le matrici~ Qed~ Rtali cheA =~ Q~ Rsi ricavano in Matlab attraverso il comando[Q,R]=qr(A,0). Calcolare l'errorekx 2 x exk 2e visualizzarlo in scala logaritmica sul graco precedente. Che cosa si osserva ? Esercizio 2 Si consideri il sistema lineareAx=bdove la matriceAè denita da A =2 42 1 0 1 21 01 23 5eb=2 41 0 13 5: Si consideri ora il seguente metodo iterativo :Lx( k+1) = Lx( k) +(bAx( k) ); k0;(1) dove >0è un parametro reale e positivo eLè la parte triangolare inferiore diA: L =2 42 0 0 1 2 0 01 23 5:1 a)Vericare se il metodo (1) è consistente. b)Riscrivere il metodo (1) nella formax( k+1) = Bx( k) +z , k0, esplicitando la matriceB . Stabilire per quali valori del parametro reale >0il metodo (1) converge. c)Determinare il parametro di convergenza ottimale opt. Esercizio 3 Si consideri il sistema lineareAx=bdove A=2 4  0  0 3 5 e; ; 2Rsono tre parametri reali. a)Senza costruire le matrici d'iterazione, si ricavino condizioni sucienti sui parametri, e tali che : i)il metodo di Gauss-Seidel converga ; ii)il metodo di Jacobi e quello di Gauss-Seidel siano entrambi convergenti. b)Scrivere la matrice d'iterazioneB Jdel metodo di Jacobi e la matrice d'iterazione B GSdel metodo di Gauss-Seidel (si ricordi che l'inversa di una matrice triangolare inferiore è una matrice triangolare inferiore). Si calcoli il raggio spettrale di queste matrici e si indichino le condizioni necessarie e sucienti su; ; anché i metodi siano convergenti. Secondo la teoria, se la matriceAè tridiagonale allora (B GS) = (B J)2 : si verichi numericamente questa proprietà. c)Per la risoluzione del sistemaAx=bsi consideri ora il metodo di Richardson stazionario precondi- zionato :D(x( k+1) x( k) ) =r( k) ; k0; essendoDuna matrice diagonale i cui elementi coincidono con gli elementi diagonali diA. Nel caso in cuiAsia una matrice simmetrica denita positiva, si calcoli il valore ottimale optdel parametro . d)In corrispondenza del valore= opt, si calcoli il fattore Cdi riduzione dell'errore in modo tale che la seguente stima sia soddisfatta : kx( k+1) xk A Ckx( k) xk A; k 0: e)Sapendo chekx(0) xk A , trovare il più piccolo interoka partire dal quale sia vericata la seguente disuguaglianza :kx( k) xk A ", nel caso in cui = 1, = 2 4 ,=p3 .2