Exercise 09 Solution

Page 1

MATEMATICA NUMERICA A.A. 2018 - 2019 Ingegneria Matematica Prof. A. Quarteroni Prof. A. Manzoni, Dr. I. Fumagalli Esercitazione 9 - Soluzione Metodi iterativi per sistemi lineari (2) Esercizio 1 Sia A∈ Rn×n una matrice simmetrica e definita positiva e si consideri il metodo del gradiente coniugato per risolvere il sistema lineareAx = b : dato x(0), posto r(0) = b− Ax(0) e p(0) = r(0), si calcola x(k+1) = x(k) +αkp(k), r(k+1) = r(k)−αkAp(k), p(k+1) = r(k+1)−βkp(k), con αk = (p(k), r(k)) (p(k), Ap(k)), βk = (p(k), Ar(k+1)) (p(k), Ap(k)) . a) Procedendo per induzione sull’interok≥ 0, si dimostrino le relazioni seguenti : (r(k+1), p(i)) = 0 i = 0,...,k, (p(k+1), Ap(i)) = 0 i = 0,...,k. Occorrerà osservare che per ognim≥ 0, si ha r(m)∈Vm = span{r(0), Ar(0),..., Amr(0)}, p(m)∈Vm. b) Sfruttando quanto trovato al punto precedente, dimostrare che (in aritmetica esatta) il metodo del gradiente coniugato termina al più dopon iterazioni. c) Siano P−1, P−1/2 due matrici simmetriche e definite positive tali cheP−1/2P−1/2 = P−1, e si consideri il seguente sistema precondizionato P−1/2AP−1/2    ˆA P1/2x ˆx = P−1/2b   ˆb Applicando il metodo del gradiente coniugato al sistema precondizionatoˆAˆx =ˆb, si derivi il metodo del gradiente coniugato precondizionato per il sistemaAx = b. In particolare, si evidenzino il ruolo del residuo precondizionato z(k) = P−1r(k) e della direzione di discesap(k) = P−1/2ˆp(k), doveˆp(k) denota la direzione di discesa del gradiente coniugato per il sistemaˆAˆx =ˆb. Soluzione 1 a) Per dimostrare la proprietà richiesta, procediamo per induzione. Supponiamo che, per un arbitrario interok≥ 1, sia (r(k), p(i)) = 0 i = 0,...,k − 1, (p(k), Ap(i)) = 0 i = 0,...,k − 1. Vogliamo dimostrare che allora vale (r(k+1), p(i)) = 0 i = 0,...,k, (p(k+1), Ap(i)) = 0…