Teorema di Kantorovich - Kantorovich theorem

Il teorema di Kantorovich , o teorema di Newton-Kantorovich, è un'affermazione matematica sulla convergenza semi-locale del metodo di Newton . Fu affermato per la prima volta da Leonid Kantorovich nel 1948. È simile alla forma del teorema del punto fisso di Banach , sebbene affermi l'esistenza e l'unicità di uno zero piuttosto che un punto fisso .

Il metodo di Newton costruisce una sequenza di punti che in determinate condizioni convergeranno a una soluzione di un'equazione oa una soluzione vettoriale di un sistema di equazioni . Il teorema di Kantorovich dà condizioni sul punto iniziale di questa successione. Se queste condizioni sono soddisfatte, esiste una soluzione vicina al punto iniziale e la sequenza converge a quel punto. ${\displaystyle x}$${\displaystyle f(x)=0}$${\displaystyle F(x)=0}$

Ipotesi

Sia un aperto e una funzione differenziabile con uno Jacobiano che è localmente Lipschitziano (ad esempio se è due volte differenziabile). Cioè, si assume che per ogni aperto esiste una costante tale che per ogni${\displaystyle X\subset \mathbb {R} ^{n}}$${\displaystyle F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ ${\displaystyle F^{\prime }(\mathbf {x})}$${\displaystyle F}$${\displaystyle U\subset X}$${\displaystyle L>0}$${\displaystyle \mathbf {x},\mathbf {y} \in U}$

${\displaystyle \|F'(\mathbf {x})-F'(\mathbf {y})\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}$

tiene. La norma a sinistra è una norma dell'operatore compatibile con la norma del vettore a destra. Questa disuguaglianza può essere riscritta per utilizzare solo la norma vettoriale. Allora per ogni vettore la disuguaglianza ${\displaystyle \mathbf {v} \in \mathbb {R} ^{n}}$

${\displaystyle \|F'(\mathbf {x})(\mathbf {v})-F'(\mathbf {y})(\mathbf {v})\|\leq L\;\|\mathbf { x} -\mathbf {y} \|\,\|\mathbf {v} \|}$

deve tenere.

Ora scegli un punto iniziale . Assumiamo che sia invertibile e costruiamo il passo di Newton${\displaystyle \mathbf {x} _{0}\in X}$${\displaystyle F'(\mathbf {x} _{0})}$${\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).}$

L'ipotesi successiva è che non solo il punto successivo, ma l'intera pallina sia contenuta all'interno del set . Sia la costante di Lipschitz per lo Jacobiano su questa palla. ${\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}}$${\displaystyle B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$${\displaystyle X}$${\displaystyle M\leq L}$

Come ultima preparazione, costruire ricorsivamente, finché è possibile, le sequenze , , secondo ${\displaystyle (\mathbf {x} _{k})_{k}}$${\displaystyle (\mathbf {h} _{k})_{k}}$${\displaystyle (\alpha _{k})_{k}}$

${\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _ {k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf { h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{ allineato}}}$

Dichiarazione

Ora se poi ${\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}$

1. esiste una soluzione di all'interno della sfera chiusa e${\displaystyle \mathbf {x} ^{*}}$${\displaystyle F(\mathbf {x} ^{*})=0}$${\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$
2. l'iterazione di Newton che inizia in converge a con ordine di convergenza almeno lineare.${\displaystyle \mathbf {x} _{0}}$${\displaystyle \mathbf {x} ^{*}}$

Un'affermazione più precisa ma leggermente più difficile da dimostrare utilizza le radici del polinomio quadratico ${\displaystyle t^{\ast }\leq t^{**}}$

${\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\ destra)t^{2}-t+\|\mathbf {h} _{0}\|}$,

${\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha _{0}} }}}}$

e il loro rapporto

${\displaystyle \theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}} +{\sqrt {1-2\alpha _{0}}}}}.}$

Quindi

1. esiste una soluzione all'interno della sfera chiusa${\displaystyle \mathbf {x} ^{*}}$${\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf { x} _{0},t^{*})}$
2. è unico all'interno della palla più grande ${\displaystyle B(\mathbf {x} _{0},t^{*\ast })}$
3. e la convergenza alla soluzione di è dominata dalla convergenza dell'iterazione di Newton del polinomio quadratico verso la sua radice più piccola , se , allora ${\displaystyle F}$${\displaystyle p(t)}$${\displaystyle t^{\ast }}$${\displaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}}$

   ${\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.}$

4. La convergenza quadratica si ottiene dalla stima dell'errore

   ${\displaystyle \|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n +1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0 }\|.}$

Corollario

Nel 1986, Yamamoto dimostrò che le valutazioni degli errori del metodo di Newton come Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra-Ptak (1980), Miel (1981), Potra (1984) , può essere derivato dal teorema di Kantorovich.

generalizzazioni

Esiste un q- analogo per il teorema di Kantorovich. Per altre generalizzazioni/variazioni, vedere Ortega & Rheinboldt (1970).

Applicazioni

Oishi e Tanabe hanno affermato che il teorema di Kantorovich può essere applicato per ottenere soluzioni affidabili di programmazione lineare .

Riferimenti

Ulteriori letture

• John H. Hubbard e Barbara Burke Hubbard: Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach , Matrix Editions, ISBN  978-0-9715766-3-6 ( anteprima della 3. edizione e materiale di esempio incluso Kant.-thm . )
• Yamamoto, Tetsuro (2001). "Sviluppi storici nell'analisi della convergenza per i metodi di Newton e simili a Newton". In Brezinski, C.; Wuytack, L. (a cura di). Analisi numerica: sviluppi storici nel XX secolo . Olanda Settentrionale. pp. 241–263. ISBN 0-444-50617-9.