%        File: analisinumerica.tex
%
% (c) Copyright 2008 Andrea Lo Pumo aka AlpT <alpt@freaknet.org>
%
% This source code is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as published 
% by the Free Software Foundation; either version 2 of the License,
% or (at your option) any later version.
%
% This source code is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
% Please refer to the GNU Public License for more details.
%
% You should have received a copy of the GNU Public License along with
% this source code; if not, write to:
% Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
%

\documentclass[a4paper]{article}
%%% 	 Orientamento	      %%%
%\usepackage[landscape]{geometry}
%%%			      %%%

\usepackage{xr-hyper}
\usepackage{amath}
\externaldocument[AII-]{analisiII}[../2/analisiII.pdf]
\externaldocument[AIII-]{analisiIII}[../3/analisiIII.pdf]
\externaldocument[AI-]{analisiI}[../1/analisiI.pdf]
\externaldocument[AL-]{alineare}[../../algebra/lineare/alineare.pdf]
\externaldocument[TOP-]{topologia}[../../topologia/topologia.pdf]
\externaldocument[CII-]{calcoloII}[../2/calcoloII.pdf]
\externaldocument[GII-]{geometriaII}[../../geometria/2/geometriaII.pdf]
\ifpdf
\usepackage{pdfpages}
\newcommand{\AII}[1]{\T{[AII,\ref{AII-#1},pg.\pageref{AII-#1}]}}
\newcommand{\AIII}[1]{\T{[AIII,\ref{AIII-#1},pg.\pageref{AIII-#1}]}}
\newcommand{\AI}[1]{\T{[AI,\ref{AI-#1},pg.\pageref{AI-#1}]}}
\newcommand{\AL}[1]{\T{[AL,\ref{AL-#1},pg.\pageref{AL-#1}]}}
\newcommand{\TOP}[1]{\T{[TOP,\ref{TOP-#1},pg.\pageref{TOP-#1}]}}
\newcommand{\CII}[1]{\T{[CII,\ref{CII-#1},pg.\pageref{CII-#1}]}}
\newcommand{\GII}[1]{\T{[GII,\ref{GII-#1},pg.\pageref{GII-#1}]}}
\else
\newcommand{\AII}[1]{\T{[AII,x.y.z,pg.xx]}}
\newcommand{\AIII}[1]{\T{[AIII,x.y.z,pg.xx]}}
\newcommand{\AI}[1]{\T{[AI,x.y.z,pg.xx]}}
\newcommand{\AL}[1]{\T{[AL,x.y.z,pg.xx]}}
\newcommand{\TOP}[1]{\T{[TOP,x.y.z,pg.xx]}}
\newcommand{\CII}[1]{\T{[CII,x.y.z,pg.xx]}}
\newcommand{\GII}[1]{\T{[GII,x.y.z,pg.xx]}}
\let\oldlabel\label
\renewcommand{\label}[1]{ [#1] \oldlabel{#1}}
\fi

\def\vz{{\underline{0}}}

\begin{document}
\title{Analisi Numerica}
\author{AlpT (@freaknet.org)\\
\small{\url{http://freaknet.org/alpt}}
}


\pagenumbering{roman}
\maketitle{}

\begin{abstract}
Questo testo e' una rielaborazione personale degli appunti presi durante
il corso di Analisi Numerica, tenuto dal Prof. Giovanni Russo\footnote{Sito
web del Prof. Russo:
\url{http://www.dmi.unict.it/~russo/}}
presso il dipartimento di
Matematica, Catania, A.A. 2007/2008.\\
Saro' ben lieto di correggere ogni eventuale errore che mi comunicherai.

Buon lettura.
\begin{center}
	\verb|^_^|
\end{center}
\end{abstract}

\input{gpl}

\clearpage
\tableofcontents
\clearpage
\pagenumbering{arabic}

\let\oldsection\section
\renewcommand{\section}[1]{\oldsection{#1}\ilabel{#1}}
\let\oldsubsection\subsection
\renewcommand{\subsection}[1]{\oldsubsection{#1}\ilabel{#1}}
\let\oldsubsubsection\subsubsection
\renewcommand{\subsubsection}[1]{\oldsubsubsection{#1}\ilabel{#1}}

\def\R{{\mathbb{R}}}
\def\rd{{\mathbb{R}^2}}
\def\C{{\mathbb{C}}}
\def\V{{\textbf{V}}}
\def\K{{\mathbb{K}}}
\def\.{{\cdot}}
\def\Sym{{\operatorname{Sym}}}
\def\rn{{\R^n}}
\def\Let{{\textbf{Sia} }\;}
\def\Sia{\Let}
\def\Se{{\textbf{Se }\;}}
\def\While{{\textbf{While }\;}}
\newcommand{\Ll}[1]{\mathcal{L}\pton{#1}}

\section{ChangeLog / Correzioni / Errata}
Cristina Oliveri ha segnalato alcune correzioni che potete trovare qui:
\url{http://www.freaknet.org/alpt/math/appunti/PDF/analisi/numerica/analisi-numerica-patch-Cristina-Oliveri.pdf}.
%Prima o poi verrano direttamente applicate direttamente a questo documento ( potete trovare i sorgenti qui: \url{http://www.freaknet.org/alpt/math/appunti/analisi/numerica/} )

\include{varie}
\section{Preliminari}
\begin{defn}
Definiamo il costo di un algoritmo numerico, misurato in \iemph{flops} (Floating Point
Operations), come il numero di divisioni e moltiplicazioni che l'algoritmo
esegue.\\
Useremo la seguente scrittura per il calcolo del costo di un algoritmo: 
\begin{enumerate}
	\item Il costo della procedura $\alpha$, verra' indicato con
		$\pqua{\alpha}$
	\item Verranno evidenziate le operazioni usate con degli
		opportuni simboli (operazione *, divisione /)
	\item Ogni operazione verra' sostituita da un 1. Tutte le
		non-operazioni verranno eliminate
\end{enumerate}
Definizioni:
\eal{&\pqua{a*b}\definizione{=}\pqua{a/b}=1\\
&\pqua{a\pm b}\definizione{=}0
}
Come esempio completo, vedi il calcolo del costo dell'algoritmo \see{propsoluztriang}.
\end{defn}
\begin{prop}
	Siano $m,n\in \mathbb{N},\;a,b,\lambda \in \mathbb{R},\;X\in \R^{p}$, si ha
	\eal{&\pqua{\sum_{i=m}^{n} x_i}=\sum_{i=m}^n[x_i]\\
	&[n!]=n-1\\
	&[(a+b)^2]=1\\
	&[\lambda X] = p
	}
\end{prop}
\begin{defn}
	Date due successioni $\pgra{x_n},\pgra{y_n}$, poniamo
	\eal{&x_n=O(y_n)\definizione{\=}\exists C,N\in \mathbb{R}:\;\;
	|x_n|\le C|y_n|\;\;\forall n> N
	}
	Usiamo la seguente convenzione:
	\eal{&a=b+O(y_n)\definizione{\=} a-b=O(y_n)}
\end{defn}
\begin{exemp}
	Preso $k>1$
	\eal{
	&\frac{n^3}{k}+ n = O(n^3),\T{ infatti,}\\
	&\qq \frac{n^3}{k}+ n \le n^3+ n \le 2n^3 \;\;\forall n\ge 1\\
	&\frac{n^3}{k}+ n = O\pton{\frac{n^3}{k}},\T{ infatti,}\\
	&\qq \frac{n^3}{k}+ n \le 2\frac{n^3}{k} \;\;\forall n\ge
	\sqrt{k}
	}
\end{exemp}
\begin{defn}
	Date due funzioni $f(x),g(x):I\(\mathbb{R}\longrightarrow
	\mathbb{R}$, dato $x_0\in I$, poniamo
	\eal{&f(x)=O_{x_0}(g(x))\definizione{\=}\exists C,r\in \R,\;r>0:\;\;|f(x)|\le
	C|g(x)|\;\;\forall x\in ]x_0-r,x_0+r[
	}
	Adottiamo la seguente convenzione:
	\eal{&f(x)=O(g(x))\definizione{\=}f(x)=O_0(g(x))
	}
\end{defn}
\begin{defn}
	Date due funzioni $f(x),g(x):I\(\mathbb{R}\longrightarrow
	\mathbb{R}$, dato $x_0\in I$, poniamo
	\eal{&f(x)=o_{x_0}(g(x))\definizione{\=}\exists r>0,\;\exists
	k(x):]x_0-r,x_0+r[ \longrightarrow  \R_+\T{ tale che }
	\sist{|f(x)|\le k(x)|g(x)|\;\;\forall x\in ]x_0-r,x_0+r[\\
	\lim_{x\to x_0} k(x)=0}
	}
	Adottiamo la seguente convenzione:
	\eal{&f(x)=o(g(x))\definizione{\=}f(x)=o_0(g(x))
	}
\end{defn}

\section{Norme}
\begin{prop}\label{normep}
	Consideriamo lo spazio vettoriale $\R^{n}$ o $\C^n$ e sia
	$v=(v_1,\dots,v_n)$ un
	suo vettore. Si puo' dimostrare che le
seguenti funzioni sono delle norme:
\eal{
&\norm{v}_1=\sumin |v_i|\\
&\norm{v}_2=\sqrt{\sumin |v_i|^2}\\
&\norm{v}_3=\pton{\sumin |v_i|^3}^{\frac{1}{3}}\\
&\vdots\\
&\norm{v}_p=\pton{\sumin |v_i|^p}^{\frac{1}{p}}\\
&\\
&\norm{v}_{\8}=\max\{|v_i|\;|\;i=1,\dots,n\}
}
\end{prop}
\begin{prop}
\eal{&\lim_{p\to +\8}\norm{v}_p = \norm{v}_{\8}}
\end{prop}
\begin{proof}
Sia \eal{&
|v_k|=\max\{|v_i|\;|\;i=1,\dots,n\} = \norm{v}_{\8}\\
&\qq \> |v_k| \ge |v_i|\;\;\forall i\= 1\ge \frac{|v_i|}{|v_k|}\ge 0\;\forall
i\\
&\qq \> 1\ge \ubrace{\lim_{p\to+\8} \pton{\frac{|v_i|}{|v_k|}}^p}{s_i}\ge 0\\
&s:=\lim \sumin \pton{\frac{|v_i|}{|v_k|}}^p = \sumin s_i\;\;(1)
}
Se $|v_k|=0$, la tesi e' vera. Supponiamo che $|v_k| \neq 0$.\\
Si ha:
\eal{
&\norm{v}_p 
= \pton{\sumin |v_i|^p}^{\frac{1}{p}}
= \pton{|v_k|^p\sumin \pton{\frac{|v_i|}{|v_k|}}^p}^{\frac{1}{p}}
=|v_k| \pton{\sumin \pton{\frac{|v_i|}{|v_k|}}^p}^{\frac{1}{p}\;\;(2)
}\\
&\lim_{p\to+\8} \norm{v}_p  \ubrace{=}{(1),(2)} \lim_{p\to+\8} |v_k|s^{\frac{1}{p}} =
|v_k|s^0=|v_k|
}
\end{proof}
\begin{defn}
	\label{defnormaequiv}
	Siano $\norm{-},\;\norm{-}'$ due norme. Poniamo
\eal{&\norm{-}\sim \norm{-}' \= \exists m,M>0:\; 
m\norm{v}\le \norm{v}'\le M\norm{v}\;\;\forall v\in \V
}
\end{defn}
\begin{prop}
	La relazione definita in \see{defnormaequiv} e' una  relazione
	d'equivalenza.
\end{prop}
\begin{proof}
	\def\norm#1{{N(#1)}}
\begin{enumerate}
	\item E' riflessiva: $\norm{-}\sim \norm{-}$, infatti,
		\eal{&\norm{v}\le \norm{v} \le \norm{v}\;\;\forall v\in \V
		}
	\item E' simmetrica: $\norm{-}\sim \norm{-}'\>\norm{-}'\sim\norm{-}$,
		infatti,
	\eal{&\norm{-}\sim \norm{-}' \= m\norm{v}\le \norm{v}'\le M\norm{v}
	\> \frac{1}{M}\norm{v}'\le \norm{v}\le \frac{1}{m}\norm{v}'
}
\item E' transitiva:
	$\norm{-}\sim \norm{-}'\sim \norm{-}''\>\norm{-}\sim\norm{-}''$,
	infatti,
\eal{&\norm{-}\sim \norm{-}'\=  m\norm{v}\le \norm{v}'\le M\norm{v}\\
&\norm{-}'\sim \norm{-}''\=  b\norm{v}'\le \norm{v}''\le B\norm{v}'\\
& bm\norm{v}\le b\norm{v}' \le \norm{v}'' \le B\norm{v}' \le BM\norm{v}
\= \norm{-}\sim\norm{-}''
}
\end{enumerate}
\end{proof}
\begin{thm}\label{thmtuttenormeequiv}
Tutte le norme in uno spazio vettoriale $\V$ di dimensione finita $n$ sono
equivalenti.
\end{thm}
\begin{proof}
\def\norm{{N}}
\def\n{{N_0}}
\eal{&\dim \V=n \> \exists B=\pgra{e_1,\dots,e_n}\T{ base di }\V}
Definiamo la funzione:
\eal{&\n:\V\longrightarrow \mathbb{R}_+\\
&\n(v)=\max \pgra{|v_i|\;|\;i=1,\dots,n}
}
dove con $v_i$ abbiamo indicato la $i$-esima componente di $v$ secondo $B$,
ovvero:
\eal{&v_i=(\coord{v}{B})_{i}}
\step{}{$\n$ e' una norma}
\begin{prova}
	\begin{enumerate}
		\item $\n(v)\ge 0$
		\item $\n(v)=0\= v=\vz$
		\item $\n(kv)=|k|\n(v)$, infatti,
	\eal{&\n(kv)=\max
	\pgra{|(\coord{kv}{B})_{i}|=|k(\coord{v}{B})_{i}|\;|\;i=1,\dots,n}=|k|\n(v)
			}
	\item $\n(v+w)\le \n(v)+\n(w)$, infatti,
\eal{&\n(v+w)=\max \pgra{|(v+w)_i|=|v_i+w_i|\;|\;i=1,\dots,n}=|v_k+w_k|\le
|v_k|+|w_k| \le  \n(v)+\n(w)}
\end{enumerate}
\end{prova}
\step{}{Dimostriamo che una qualsiasi norma $N$ e' equivalente a $\n$. Cosi'
avremo acquisito la tesi.}
\begin{prova}
Basta dimostrare che
\eal{&\exists m,M>0:\;m\n(v)\le N(v)\le M\n(v)\;\;\forall \v\in\V
}
Per $v=\vz$ la tesi e' vera. Consideriamo quindi solo vettori non nulli.
\step{stepM}{Dim. $\exists M$}
\begin{prova}
	\eal{&\T{Sia }H=\max_{i=1,\dots,n}N(e_i)\\
	&N(v)=N\pton{\sumin v_ie_i} \le \sumin N(v_ie_i)
	= \sumin |v_i|N(e_i) \le \sumin \n(v)H =nH\n(v)}
Quindi $M=nH$
\end{prova}
\step{}{Dim $\exists m$}
\begin{prova}
$(\V,d)$ e' uno spazio metrico, dove 
\eal{&d(v,w)=\n(w-v)}
e' una metrica.\\
$N$ e' allora una funzione dallo spazio metrico $(\V,d)$ allo spazio metrico
$(\R,d_e)$, dove $d_e$ e' la norma euclidea. Possiamo quindi applicare a $N$ i thm di analisi II.\\
Si prova che $\n()$ e' una funzione continua in $\V$.
\end{prova}
\step{}{$N()$ e' continua}
\begin{prova}
\eal{&
\n\T{ continua in }x\>
\lim_{x\to x_0}\n(x)=\n(x_0) \= \lim_{x\to x_0}|\n(x)-\n(x_0)|=0\\
&\sist{0\le |N(x)-N(x_0)| \ubrace{\le }{\T{\stepref{stepM}}}
M|\n(x)-\n(x_0)|\\
0\longrightarrow 0\\
M|\n(x_n)-\n(x)|\longrightarrow 0
} \ubrace{\>}{\AII{thmlimitism}} \lim_{x\to x_0} |N(x)-N(x_0)|=0\=
 \lim_{x\to x_0} N(x) = N(x_0)
}
Quindi $N()$ e' continua.
\end{prova}
\step{}{$\exists m$}
\begin{prova}
Sia data la $n$-sfera secondo la norma $\n$:
\eal{&S_n=\pgra{v\in \V\;|\;\n(v)=1}}
$S_n$ e' un insieme sequenzialmente compatto.\\
Allora, poiche' $N$ e' continua in $S_n$, per il thm di Weierstrass (vedi
\AII{weierstrass}) si ha
\eal{&\exists c=\min N(S_n),\;\;\exists C=\max N(S_n)>0
}
allora,
\eal{&\frac{v}{\n(v)}\in S_n\> N\pton{\frac{v}{\n(v)}} = \frac{N(v)}{\n(v)}
\ge c
\= N(v)\ge c\n(v)
}
Quindi $m=c$
\end{prova}
\end{prova}
\end{proof}
%\begin{defn}
%	Sia $\K^{n\*m}$ uno spazio vettoriale di matrici $n\*m$ sul campo
%	$\K$. Definiamo la norma matriciale su $\K^{n\*m}$:
%	\eal{&\T{Data }N:\K^{n\*m}\longrightarrow \mathbb{R}_+\\
%	&N\T{ e' un norma matriciale }\= \T{ e' una norma su }\K^{n\*m}, \T{
%	ed inoltre, }N(AB)\le N(A)N(B)
%	}
%	dove $AB$ e' l'usuale prodotto tra matrici.
%\end{defn}
\begin{defn}\label{normamat}
	\ilabel{norma matriciale}
	Sia $A\in \K^{n\*m}$, utilizzando le norme viste in \see{normep}, definiamo
	\eal{&\norm{A}_{p,q}\definizione{=}\sup\pgra{\frac{
	\norm{Ax}_p}{\norm{x}_q}\;|\;x\in \K^{m\*1},\;x \neq 0}\\
	&\norm{A}_p\definizione{=}\norm{A}_{p,p}
	}
	chiamata norma matriciale, indotta da $\norm{-}_p,\norm{-}_q$.\\
	Definiamo la trasposta coniugata di una matrice complessa:
	\eal{&\TRC A=\ove{\TR A}}
	ovvero, $\TRC A$, e' la matrice coniugata\footnote{$(\ove A)_{ij}=\ove
	a_{ij}$} della trasposta di $A$. Se $A$ e' reale, la trasposta
	coniugata coincide con l'usuale trasposta.\\
	Useremo anche la seguente convenzione:
	\eal{&|a|=\sqrt{a\ove a}=\sist{\T{valore assoluto di }a&a\in\R\\
	\T{modulo di }a & a\in \C}}
	Definiamo il \iemph{raggio spettrale} di $A$:
	\eal{&\rho(A)=\max\{|\lambda| \;|\;\lambda\T{ autovalore di }A\}
	}
	Il prodotto scalare su $\K^n$, con $\K=\R$ oppure $\K=\C$, e' definito
	come:
	\eal{
	&\T{se }x,y\in \K^{1,n}:\;\; x\.y\definizione{=} x\TRC y\\
	&\T{se }x,y\in \K^{n,1}:\;\; x\.y\definizione{=} \TRC x y 
	}
	Se $\K=\R$, $\.$ si riduce al prodotto scalare standard.
\end{defn}

\begin{prop}
	\label{propnormamatresplicita}
	Sia $A\in \K^{n\*m}$, si ha
\eal{
&1.\;\;\norm{A}_{p,q}=\max\pgra{\norm{Ax}_p\;|\;x\in
\K^{m\*1},\;\norm{x}_q=1}}
Supponendo $\K=\R$, si ha
\eal{
&2.\;\;\norm{A}_{\8}=\max_{1\le i\le n}\sumjm|a_{ij}|\\
&3.\;\;\norm{A}_1=\max_{1\le j\le  m} \sumin |a_{ij}|\\
&4.\;\;\norm{A}_1=\norm{\TR A}_{\8}\\
&5.\;\;\norm{A}_2=\sqrt{\rho(\TR AA)}\\
&5.1\;\;A=\TR A \> \norm{A}_2=\rho(A)}
dove $\rho$ e' il raggio spettrale.
\end{prop}
\begin{proof}
	\step{}{Dim $1.$}
	\begin{prova}
		Sia \eal{&\lambda = \norm{x}_q\\
		&\ove x=\frac{x}{\norm{x}_q}\qq\T{ e' il versore di }x\\
		&\qq \norm{\ove x}_q=1\;\;(*)\\
		&x=\lambda\ove x\\
		} 
		Osserviamo che:
\eal{& \frac{\norm{A x}_p}{\norm{x}_q} =
\frac{\norm{A\lambda \ove x}_p}{\norm{\lambda\ove x}_q} =
\frac{ |\lambda|\norm{A\ove x}_p}{|\lambda|\norm{\ove x}_q}=
\frac{\norm{A\ove x}_p}{\norm{\ove x}_q} \ubrace{=}{(*)}  \norm{A\ove x}_p
}
Quindi, basta limitarsi a considerare i versori, ovvero consideriamo tutti e
soli i vettori di $S_n=\pgra{x\;|\;x\in \K^{m\*1},\; \norm{x}_q=1}$\\
Consideriamo la funzione $N'(x)=\norm{Ax}_p$. $N'(x)$ e' continua, perche'
composizione di funzioni continue\footnote{$Ax$ e' continua perche'
composizione di funzioni lineari. $N(x)=\norm{x}_p$ e' continua per quanto
visto  in \see{thmtuttenormeequiv}}. Allora, procedendo come nella dim. del
thm \see{thmtuttenormeequiv}, deduciamo che $N'(x)$ ammette minimo e massimo
su $S_n$, e quindi 
\eal{&\sup_{x\in S_n}N'(x)=\max_{x\in S_n}N'(x)}
	\end{prova}
	\step{}{Dim. $2.$}
	\begin{prova}
		\def\n#1{{\norm{#1}_{\8}}}
		Ridefiniamo $S_n$ secondo la norma $\n{-}$:
		\eal{&S_n=\pgra{x\;|\;x\in \K^{m\*1},\; \n{x}=1}}
Si ha
		\eal{&\norm{A}_{\8} \ubrace{=}{1.} 
		\max_{x\in S_n} \n{Ax}\;\;(2)\\
		&\n{Ax}=\max_{1\le i\le n}|(Ax)_i|=
		\max_{1\le i\le n} |\sumjm a_{ij}x_j|\;\;(2.1)
		}
		\step{p1}{$\exists c\ge 0:\;\n{Ax}\le c\;\forall x\in S_n$}
		\begin{prova}
	\eal{
	&x\in S_n\> \n{x} =1 \= \max |x_h| =1 \= |x_h|\le  1\;\forall
	h=1,2,\dots,m\;\;(*)\\
	& |\sumjm a_{ij}x_j|\le  \sumjm |a_{ij}| |x_j|
	\le \sumjm |a_{ij}| =:c_i\\
	&\T{Sia }c=\max_{i=1,\dots,n}c_i\\
	&\n{Ax}\ubrace{\le}{(2.1)} \max_{1\le i\le n} c_i = c
			}
		\end{prova}
		\step{p2}{$\exists  \ove x\in S_n:\;\n{A \ove x} \ge  c$}
		\begin{prova}
			\eal{&c=\max_{i=1,\dots,n}c_i=c_k=\sumjm |a_{kj}| \\
			&\qq \> c\ge \sumjm |a_{ij}| \;\;\forall
			i=1,\dots,n\;\;(3)
			}
			Scegliamo la seguente $x$:
			\eal{&x_j=\sist{1&a_{kj}\ge 0\\-1&a_{kj}<0}\;\;(**)}
			si ha
			\eal{&
			(Ax)_k = \sumjm a_{kj}x_j  \ubrace{=}{(**)} \sumjm
			|a_{kj}| =c_k=c\\
			&\n{Ax}=\max_{1\le i\le n}|(Ax)_i| \ge |(A_x)_k|
			=c\\
			&\n{Ax}\ge c
			}
		\end{prova}
		\qedstep
		\begin{prova}
			Sia 
			\eal{&\n{Ay}=\max_{x\in S_n}\n{Ax}
			}
			Il passo \stepref{p1} implica che
			\eal{&\forall x\in S_n\;\n{A x}\le c\>\n{Ay} \le  c
			\=
			\max_{x\in S_n}\n{Ax}\le
			c
			}
			Il passo \stepref{p2} implica che
			\eal{&\max_{x\in S_n}\n{Ax} \ge \n{A\ove x}\ge c
			}
			Quindi
			\eal{&
			\max_{x\in S_n}\n{Ax} \le \ge  c \=\max_{x\in
			S_n}\n{Ax} =c\= \n{A}=c= \max_{i=1,\dots,n}\sumjm |a_{ij}|
			}
		\end{prova}
	\end{prova}
	\step{}{Dim  $4.$}
	\begin{prova}
		Immediata conseguenza della $2.,3.$.
	\end{prova}
	\step{}{Dim $5.$}
	\begin{prova}
		\def\n(#1){{\norm{#1}_2}}
		\step{max}{Osserviamo che dati $n$ numeri reali o complessi $s_1,\dots,s_n$, si ha
		\eal{&\pton{\max\pgra{|s_1|,\dots,|s_n|}}^2=\max\pgra{|s_1|^2,\dots,|s_n|^2}}
		}
		\begin{prova}
		Infatti, sia $|s|=\max\pgra{|s_1|,\dots,|s_n|}$, allora
\eal{&|s| \ge  |s_i|\;\;\forall i=1,\dots,n\> |s|^2 \ge  |s_i|^2 \;\;\forall i=1,\dots,n
\> |s|^2=\max\pgra{|s_1|^2,\dots,|s_n|^2}
		}
		\end{prova}
		Abbiamo:
			\eal{&\n(A) \ubrace{=}{1.} \max \pgra{\n(Ax)
			\;|\;\n(x)=1}}
		\step{nquadro}{Dim. che $\n(Ax)^2=\TR xC x$, con $C\in \Sym_m(\R)$ }
		\begin{prova}
			Fissiamo adesso una $x:\;\n(x)=1$, si ha 
		\eal{
		&\n(Ax)=\sqrt{\sumin |(Ax)_i|^2}\\
		&\n(Ax)^2 = Ax\.Ax = \TR (Ax)Ax=\TR x\TR A A x
		}
		Sia $C=\TR A A\in \R^{m\*m}$. $C$ e' simmetrica, infatti,
		\eal{&\TR C = \TR \pton{\TR A A} = \TR A A = C
		}
	\end{prova}

		Allora per quanto visto in Geometria II:
		\eal{&C\in \Sym_m(\R)
		\ubrace{\>}{\GII{corspettrI}}
		\exists B=\pgra{u_1,\dots,u_m}\T{ base ortonormale di
		}\mathbb{R}^m:\;\;u_i \T{ sono autovettori di }C\\
		&B\T{ ortonormale } \> \sist{\n(u_i)=1\;\;\forall
		i=1,\dots,m\\
		u_i\perp u_j\=u_i\.u_j=0\;\;\forall i \neq j}
		}
		Sia $\lambda_i$ l'autovalore di $u_i$, ovvero
		\eal{&Cu_i= \lambda_iu_i}
		Per il lemma \GII{lemspettro}, si ha $\lambda_i\in
		\R\;\;\forall i=1,\dots,m$.
		\step{maxlambda}{Dim. che $\max\pgra{|\lambda_i|\;|\;i=1,\dots,m}=\rho(C)$}
		\begin{prova}
		Se costruiamo $B$ usando il metodo descritto in
		\GII{thmspettrale}, allora $\pgra{\lambda_i\;|\;i=1,\dots,m}$
		e' l'insieme di tutti gli autovalori di $C$ (puo' anche darsi
		che $\lambda_i=\lambda_j$ per qualche $i \neq j$).\\
		Quindi, per definizione (\vedi{raggio spettrale}), si ha
		\eal{&\max\pgra{|\lambda_i|\;|\;i=1,\dots,m}=\rho(C)}
		\end{prova}

		\step{lnonneg}{$\lambda_i\ge 0\;\;\forall i=1,\dots,m$}
		\begin{prova}
			\eal{&\n(Au_i)^2 \ubrace{=}{\sref{nquadro}} \TR u_i C u_i =\TR u_i \lambda_i u_i = 
		\lambda_i\TR u_iu_i=\lambda_iu_i\.u_i=\lambda_i \n(u_i)
		\\
		&\lambda_i \n(u_i) = \n(Au_i)^2 \ge 0\= \lambda_i \ge 0
		}
		\end{prova}

		\def\a{{\alpha}}
		\step{cambiobase}{Dim. che \eal{
		&\n(Ax)^2=\sumim |\lambda_i| |\a_i|^2\\
		&\n(x)^2=\sumim |\a_i|^2
		}
		dove le $\a_i$ sono le componenti di $x$ secondo la base $B$}
		\begin{prova}
		\eal{&\sist{B\T{ base ortonormale di }\mathbb{R}^m\\
		x\in \R^m}
		\> x=\sumim \a_iu_i\\
		&\n(Ax)^2  \ubrace{=}{\sref{nquadro}} 
		\TR x C x = 
		\sumim \TR x C \a_iu_i=
		\sumim\sumjm \TR (\a_ju_j) C \a_iu_i =
		\sumim\sumjm \a_j\a_i\TR u_j C u_i \ubrace{=}{Cu_i= \lambda_iu_i}		
		\sumim\sumjm \a_j\a_i\lambda_i\TR u_j  u_i =\\
		&=
		\sumim\sumjm \a_j\a_i\lambda_iu_j\.u_i \ubrace{=}{ u_i\.u_j =0\;\;\forall i \neq j } 
		\sumim |\a_i|^2\lambda_i  u_i\.u_i=
		\sumim \lambda_i |\a_i|^2 \n(u_i)  \ubrace{=}{\n(u_i)=1} 
		\sumim \lambda_i |\a_i|^2
		\ubrace{=}{\sref{lnonneg}} 
		\sumim |\lambda_i| |\a_i|^2
		}
		Infine, 
		\eal{&B\T{ ortonormale }
		\ubrace{\>}{\GII{prodscalortonormale}} 
		x\.x=\TR [x]_B[x]_B =  \sumim |\a_i|^2\\
		&\n(x)^2=x\.x=\sumim |\a_i|^2
		}
	\end{prova}
		\qedstep
		\begin{prova}
		\eal{&
		\n(A)^2 = \pton{\max \pgra{\n(Ax)\;|\;\n(x)=1}}^2
		\ubrace{=}{\sref{max}} \max\pgra{\n(Ax)^2\;|\;\n(x)=1}\\
		&		\ubrace{=}{\sref{cambiobase}} \max \pgra{
		\sumim |\lambda_i| |\a_i|^2 \;\Big|\;
		\sumim |\a_i|^2 =1
		}\;\;(**)\\
		&\sist{|\lambda_i|\ge 0\\
		\sumim |\a_i|^2 =1 } \> \sumim  |\lambda_i| |\a_i|^2 \T{ e' una
		media pesata il cui max si ha per }
		\a_i=\delta_{ki}\;\;\forall i =1,\dots,m\\
		&\qq \T{ dove $k$ e' tale che }
		|\lambda_k|=\max\pgra{|\lambda_i|}_i \T{ Ovvero, si ha: }\\
		&\qq  \max \pgra{
                \sumim |\lambda_i| |\a_i|^2 \;\Big|\;
                \sumim |\a_i|^2 =1
		} = |\lambda_k|  \ubrace{=}{\sref{maxlambda}} \rho(C)\\
		& \ubrace{\>}{(**)}  \n(A)^2 = \rho(C)\= \n(A)=\sqrt{\rho(\TR
		A A )}
		}
		Infine, se $A$ e' simmetrica, si ha:
		\eal{&A\T{ simmetrica }\= A=\TR A \>
		\rho(C)=\rho(\TR A A) = \rho(A A)}

		\step{LM}{Siano
		$L=\pgra{\lambda_1,\dots,\lambda_m}.\;\;M=\pgra{\mu_1^2,\dots,\mu_m^2}$
		rispettivamente l'insieme di tutti gli autovalori di $C=AA$ e
		di tutti i quadrati degli autovalori di $A$.\\
		Si ha che $\mu_1,\dots,\mu_m$ sono tutti gli autovalori di
		$A$, e inoltre $L=M$.\\
		\lineapiccola\\
		}
		\begin{prova}
			Poiche' $A$ e' simmetrica, 
			\eal{&A\in \Sym_m(\R) \ubrace{\>}{\GII{corspettrI}}
			\sist{\exists \pgra{v_1,\dots,v_m}\T{ base ortornormale di
			$\R^m$,\;}\\
			v_1,\dots,v_m\T{ autovettori di $A$:} Av_i=\mu_iv_i\\
			\{\mu_1,\dots,\mu_m\}\T{ insieme di tutti gli
			autovettori di $A$}}}
			\step{}{Dim $L\)M$}
			\begin{prova}
			\eal{&\mu_i\in M \> Av_i=\mu_iv_i\\
			&Cv_i=AAv_i=A\mu_iv_i=\mu_i^2v_i\\
			&Cv_i=\mu_i^2v_i\> \mu_i^2 \in L
				}
			\end{prova}
			\step{}{Dim $L\(M$}
			\begin{prova}
			\eal{&\lambda_i\in L \> Cu_i=\lambda_i u_i\;\;[*]\\
			&u_i=\sumjm\beta_jv_j\\
			&u_i\in B\T{ base } \> u_i \neq 0\>\exists \beta_k  \neq 0\\
			&Cu_i=AAu_i=\sumjm AA\beta_jv_j=\sumjm \beta_j\mu_j^2v_j
			\ubrace{=}{[*]} \lambda_i u_i=\lambda_i \sumjm\beta_jv_j\\
			&\sumjm \beta_j\mu_j^2v_j =  \sumjm \lambda_i\beta_jv_j
			\= \sumjm (\beta_j\mu_j^2-\lambda_i\beta_j)v_j=0
			\ubrace{\=}{v_1,\dots,v_m\T{ sono l.i.}} 
			\beta_j\mu_j^2-\lambda_i\beta_j =0\;\;\forall j=1,\dots,m
			\>\\
			&\> \beta_k\mu_k^2=\lambda_i\beta_k \ubrace{\>}{k \neq 0} 
			\lambda_i=\mu_k^2\\
			&\lambda_i=\mu_k^2 \> \lambda_i\in M
			}
			\end{prova}
		\end{prova}
		\step{rhoAArhoA}{$\rho(AA)=\rho(A)^2$}
		\begin{prova}
			\eal{
			&A\in \Sym_m(\R) \ubrace{\>}{\GII{lemspettro}}
				\mu_1,\dots,\mu_m\in \R \>
				|\mu_i|^2=\mu_i^2\;\;\forall i\;\;[**]\\
			&\rho(AA)=\max L  \ubrace{=}{\sref{LM}}
			\max M =\max\pgra{\mu_1^2,\dots,\mu_m^2}
			\ubrace{=}{[**]}
			\max\pgra{|\mu_1|^2,\dots,|\mu_m|^2}=\\
			&
			\ubrace{=}{\sref{max}}
			\pton{\max\pgra{|\mu_1|,\dots,|\mu_m|}}^2 =\rho(A)^2\\
			&\rho(AA)=\rho(A)^2
			}
		\end{prova}
		In conclusione,
		\eal{&\n(A)=\sqrt{\rho(A A)} \ubrace{=}{\sref{rhoAArhoA}}
		\sqrt{\rho(A)^2}=|\rho(A)|=\rho(A)
		}
		\end{prova}
	\end{prova}
\end{proof}
\begin{prop}\label{normamatricesubmoltiplicativita}
	La funzione $\norm{-}_{p,q}:\K^{n\* m}\longrightarrow \mathbb{R}_+$ e'
	una norma. Inoltre, valgono le seguenti proprieta':
	\eal{&1.\;\;\norm{Ax}_{p}\le  \norm{A}_{p,q}\norm{x}_q\;\;\forall x\in
	\K^{m,1}}
	Inoltre, data $B\in \R^{m\*r}$ e data la norma $\norm{-}_{q,q}:\K^{m\*
	r}\longrightarrow \mathbb{R}_+$, si ha
	\eal{
	&2.\;\;\norm{AB}_{p,q} \le  \norm{A}_{p,q}\norm{B}_{q,q}
	}
\end{prop}
\begin{proof}
	\step{}{$\norm{-}_{p,q}$ e' una norma}
	\begin{prova}
		\def\n(#1){{\norm{#1}_{p,q}}}
	\begin{enumerate}
		\item $\n(A)\ge 0$, infatti,
		\eal{&\norm{A}_{p,q} \ubrace{=}{\see{propnormamatresplicita}}
		\max\pgra{\norm{Ax}_p\;|\;\norm{x}_q=1}=  \norm{A\ove x}_p
		\ubrace{\ge}{\norm{-}_p\T{ e' una norma}} 0
		}
	\item $\n(A)=0\= A=\vz^{n\*m}$, infatti,
		\eal{&\n(A)=\max\pgra{\frac{\norm{Ax}_p}{\norm{x}_q}\;|\;x
		\neq 0}
	\= \norm{Ax}_p=0\;\;\forall x \neq 0
	\ubrace{\=}{\norm{-}_p\T{ e' una norma}} 
	Ax=0\;\;\forall x \neq 0
	}
	Allora, scegliendo $x$ in modo opportuno, si ha:
	\eal{
	&\T{Per }x_i=\delta_{1i},\;i=1,\dots,m\T{ si ha } Ax=A^{1},\;\;{Ax}_p=0 \= A^{1}=0\\
	&\T{Per }x_i=\delta_{2i},\;i=1,\dots,m\T{ si ha } Ax=A^{2},\;\;{Ax}_p=0 \=
	A^{2}=0\\
	&\vdots\\
	&\T{Per }x_i=\delta_{ni},\;i=1,\dots,m\T{ si ha } Ax=A^{n},\;\;{Ax}_p=0 \=
	A^{n}=0}
	Quindi tutte le colonne di $A$ sono nulle, ovvero $A$ e' la matrice
	nulla.
	\item $\n(A+B)\le \n(A)+\n(B)$, infatti,
		\eal{&\n(A+B)=\max\pgra{\norm{(A+B)x}_p=\norm{Ax+Bx}_p\;|\;\norm{x}_q=1}=\norm{A\ove
		x+B\ove x}_p \le \\
		&\qq \le \norm{A\ove x}_p+\norm{B\ove x}_p
		\le \n(A)+\n(B)
		}
\end{enumerate}

	\end{prova}
	\step{}{Dim $1.$}
	\begin{prova}
	Se $\norm{x}_q=0\=x=0$, la tesi e' vera. Consideriamo quindi $x \neq
	0$.
		\eal{&
	\norm{A}_{p,q} \ubrace{=}{\see{propnormamatresplicita}}
	\max\pgra{\frac{\norm{Ax}_p}{\norm{x}_q}\;|\;x\in \K^{m\*1},\;x \neq 0} \ge
	\frac{\norm{Ax}_p}{\norm{x}_q} \;\;\forall x\in \K^{m\*1},\;x \neq 0 \=\\
	&\=  \norm{A}_{p,q}\norm{x}_q\ge \norm{Ax}_p\;\;\forall x\in
	\K^{m\*1},\;x \neq 0
	}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
		\def\n#1{{\norm{#1}_{p,q}}}
		\def\np#1{{\norm{#1}_{p}}}
		\def\nq#1{{\norm{#1}_{q}}}
		\def\nqq#1{{\norm{#1}_{q,q}}}
		\eal{
		&x\in \R^{r\*1},\;\;B\in \R^{m\*r} \> Bx \in \R^{m\*1}\;\;(1)\\
		&\np{ABx} = \np{A(Bx)}  \ubrace{\le }{(1),\;1.} \n A \nq{Bx}
		\ubrace{\le }{1.} \n A \nqq B \nq x \\
		&\frac{\np{ABx}}{\nq x} \le \n A \nqq B \;\;\forall x\in
		\R^{m\*1} \> \sup\pgra{\frac{\np{ABx}}{\nq x} }
		\le  \n A \nqq B 
		 \ubrace{\=}{\see{normamat}} 
		\n{AB} \le  \n A \nqq B
		}
	\end{prova}
\end{proof}
\begin{prop}\label{propraggiospettrale}
	Sia $\A\in \R^{n\*n}$, si ha
	\eal{&1.\;\;\rho(A)\le \norm{A}_{p,q}\;\;\forall p,q\in
	\mathbb{N}^*\\
	&2.\;\;\forall A\in \R^{n\*n}\;\forall \varepsilon > 0 \;\;\exists
	p,q\in \mathbb{R}^*,\;\T{ dipendenti da $A$ e da $\varepsilon$, tali
	che }
	\;\; \Big|\norm{A}_{p,q} -\rho(A)\Big| < \varepsilon\\
	&3.\;\;\rho(A)=\inf_{p,q\in \mathbb{N}^*} \norm{A}_{p,q}
	}
\end{prop}
\begin{prop}\label{normadueinversa}
	\def\l{{\lambda}}
		Sia $A\in \R^{n\*n}$ invertibile. Sia $\lambda_m(\TR A A)$
		l'autovalore minimo in modulo di $\TR A A $ e $\lambda_M(\TR A
		A)$ l'autovalore massimo. Si ha
	\eal{
	&1.\;\;\norm{A}_2 =\sqrt{\lambda_M(\TR AA)}\\
	&2.\;\;\norm{\inv A}_2= \frac{1}{\sqrt{\lambda_m(\TR A A)}}
	}
\end{prop}
\begin{proof}
	La $1.$ si ha direttamente per la \see{propnormamatresplicita}.\\
	Dimostriamo la $2.$\\
	Notiamo intanto che se $\lambda$ e' un autovalore di $B$ allora
	$\frac{1}{\lambda}$ e' un autovalore di $\inv B$, infatti,
	\eal{&Bu=\lambda u \> u=\inv B \lambda u \\
	&\frac{1}{\lambda} u = \inv B u
	}
	Osserviamo che $\TR A A $ e $A \TR A $ hanno gli stessi autovalori,
	infatti, 
	\eal{&A(\TR A A )\inv A = A\TR A \> \TR A A,\;A\TR A \T{ sono simili}
	\ubrace{\>}{\AL{matsimilihannoglistessiautovalori}}  
	\T{ hanno gli stessi autoval. }\;\;(1)
	}
	Se con $l_1,\dots,l_n$ indichiamo gli autovalori di $\TR A A $, e li
	ordiniamo in modo da avere
	\eal{&\lambda_M(\TR A A)=|l_1| \ge |l_2| \ge  \dots \ge  |l_n|=\lambda_m(\TR A A)}
	elevando i singoli membri per $-1$, abbiamo
	\eal{&\frac{1}{|l_1| }\le \frac{1}{ |l_2|} \le  \dots \le\frac{1}{|l_n|}
	}
	che sono gli autovalori di $\inv A \TR \inv A$, e quindi
	\eal{&\rho(\inv A) \ubrace{=}{\see{propnormamatresplicita}} 
	\sqrt{\rho(\TR \inv A \inv A)} = 
	\sqrt{\lambda_M(\TR \inv A \inv A)} = 
	\sqrt{\lambda_M(\inv{(A\TR A)})} = \frac{1}{\sqrt{\lambda_m(A\TR A)}}
	\ubrace{=}{(1)}  \frac{1}{\sqrt{\lambda_m(\TR AA)}}
	}
\end{proof}
\begin{prop}\def\l{{\lambda}}
	\label{normadueinversasimmetrica}
		Sia $A\in \R^{n\*n}$ invertibile e simmetrica. Siano
		$\pgra{\l_i}$ i suoi autovalori, ordinati come segue:
		\eal{&|\l_1| \ge |\l_2| \ge  \dots \ge |\l_n|}
		Si ha
	\eal{
	&\norm{A}_2 =|\l_1|\\
	&\norm{\inv A}_2= \frac{1}{|\l_n|}
	}
\end{prop}
\begin{proof}
	Basta ripetere la dimostrazione della prop \see{normadueinversa},
	considerando che nel caso di $A$ simmetrica si ha
	\eal{&\norm{A}_{2}=\rho(A)=\lambda_M(A)}
	e che anche $\inv A$ e' simmetrica, infatti,
	\eal{&\TR (\inv A) = \inv {(\TR A)} = \inv A
	}
\end{proof}
\section{Sistemi lineari}
\begin{prop}\label{propsoluztriang}
	Sia dato un sistema triangolare  superiore
	\eal{&Ax=b,\T{ con }A\in \R^{n\*n},\;|A| \neq 0,\;x,b,\in \R^n}
Si ha:
\eal{& x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij}x_j}{a_{ii}} \;\;\forall i=n,n-1,\dots,1}
Se $Ax=b$ e' un sistema triangolare inferiore, si ha:
\eal{&
	x_i = \frac{b_i - \sum_{j=1}^{i-1} a_{ij}x_j}{a_{ii}} \;\;\forall i=1,\dots,n
}
Il costo di questa soluzione e':
\eal{&\frac{n(n+1)}{2} 
}
\end{prop}
\begin{proof}
	\eal{&|A| \ubrace{=}{A\T{ matrice
	triangolare}}=\prod_{i=1}^{n}a_{ii}\;\;(*) \\
	&|A| \neq 0  \ubrace{\>}{(*)}  a_{ii} \neq 0\;\;\forall i=1,\dots,n}
	\step{}{Triangolare superiore}
	\begin{prova}
	\eal{
	&Ax=b \ubrace{\=}{A\T{ mat. triang. sup.}}
	\= \sum_{j=i}^n a_{ij}x_j=b_i\;\;\forall i=n,n-1,\dots,1 \=\\
	&\= a_{ii}x_i +\sum_{j=i+1}^n a_{ij}x_j=b_i\;\;\forall i=n,n-1,\dots,1\=\\
	&\= x_i = \frac{b_i - \sum_{j=i+1}^n a_{ij}x_j}{a_{ii}} \;\;\forall
	i=n,n-1,\dots,1
	}
	\end{prova}
	\step{}{Triangolare inferiore}
	\begin{prova}
	\eal{
	&Ax=b \ubrace{\=}{A\T{ mat. triang. inf.}}
	\= \sum_{j=1}^i a_{ij}x_j=b_i\;\;\forall i=1,\dots,n \=\\
	&\= a_{ii}x_i +\sum_{j=1}^{i-1} a_{ij}x_j=b_i\;\;\forall i=1,\dots,n\=\\
	&\= 
	x_i = \frac{b_i - \sum_{j=1}^{i-1} a_{ij}x_j}{a_{ii}} \;\;\forall i=1,\dots,n
	}
	\end{prova}
	\step{}{
	Calcoliamo il costo
	}
	\begin{prova}
		\eal{
		&[x_i]=\pqua{\pton{\sum_{j=i+1}^n a_{ij}*x_j}/{a_{ii}}}
		=\pqua{\sum_{j=i+1}^n a_{ij}*x_j}+\pqua{/{a_{ii}}}=\\
		&=\sum_{j=i+1}^n \pqua{a_{ij}*x_j}+1
		=(n-(i+1)+1)+1=n-i+1\\
		&\pqua{x_i\;\;\forall i=n,n-1,\dots,1}=\sum_{i=1}^{n}[x_i]
		=\sum_{i=1}^nn-i+1=
		n^2+n-\sum_{i=1}^ni \ubrace{=}{\see{sommapriminnumeri}} n^2+n-\frac{n(n+1)}{2}
		=\frac{n(n+1)}{2}
		}
	\end{prova}
\end{proof}
\begin{prop}\label{gaussnaive}
	\def\A#1{A^{\mathbf{#1}}}
	\def\a#1{a^{\mathbf{#1}}}
	\ilabel{riduzione di Gauss!naive}
	Riduzione di un sistema lineare a un sistema triangolare (riduzione
	naive di Gauss).\\
	Sia dato un sistema
	\eal{&Ax=b,\T{ con }A\in \R^{n\*n},\;|A| \neq 0,\;x,b,\in \R^n}
	Il seguente e' un algoritmo che riduce la matrice completa $\A1=(A|b)$ del
sistema $Ax=b$ alla matrice completa $\A n$ di un sistema triangolare equivalente ad
$Ax=b$:
\eal{& \pton{\A {k+1}_{i} := \A k_{i} -\frac{\a k_{ik}}{\a k_{kk}}\A k_k\;\; \forall i=k+1,\dots,n}\;\;\forall k=1,\dots,n-1 }
dove $\A k_{i}$ rappresenta l'$i$-esima riga, della matrice $\A k$.\\
\textbf{Attenzione: }stiamo supponendo che $\a k_{kk} \neq 0\;\;\forall
k=1,\dots,n-1$.\\
In forma esplicita, l'algoritmo e':
\eal{&
\pton{
\pton{\a {k+1}_{ij} := \a k_{ij} -\frac{\a k_{ik}}{\a k_{kk}}\a k_{kj}\;\;
	\forall j=k,\dots,n+1}\;\;
	\forall i=k+1,\dots,n}\;\;\forall k=1,\dots,n-1
}
Il codice ottimizzato:
	\eal{&\forall k=1,\dots,n-1\\
&\qq \forall i=k+1,\dots,n \\
&\qq \qq m:=\frac{\a k_{ik}}{\a k_{kk}}\\
&\qq\qq \forall j=k,\dots,n+1\\
&\qq\qq\qq \a {k+1}_{ij} := \a k_{ij} -m\a k_{kj}
}
Il costo di quest'ultimo codice e'
\eal{& 3\frac{(n-1)n}{2}+\frac{2(n-1)^3+3(n-1)^2+n-1}{6} \approx \frac{n^3}{3}+O(n^2)
}
Il numero $m_{ik}=\frac{\a k_{ik}}{\a k_{kk}}$, viene chiamato
\iemph{moltiplicatore} di posto $i,k$.
\end{prop}
\begin{proof}
	\def\A#1{A^{\mathbf{#1}}}
	\def\a#1{a^{\mathbf{#1}}}
	\pfsketch{Sia $\A1=(A|b)$ la matrice completa del sistema
	$Ax=b$.\\ 
	Ridurremo il sistema iniziale $\A1$, nel sistema
	equivalente $\A2$, poi $\A2$ in $\A3$, etc\dots\\
	L'idea di base consiste nell'effettuare riduzioni del seguente tipo:
	\eal{&\A1=
	\begin{bmatrix}
		\a1_{11}&\a1_{12} & \a1_{13} & \ldots & \a1_{1n}\vline&\a1_{1n+1}\\
		\a1_{21}&\a1_{22} & \a1_{23} & \ldots & \a1_{2n}\vline&\a1_{2n+1}\\
		\a1_{31}&\a1_{32} & \a1_{33} & \ldots & \a1_{3n}\vline&\a1_{3n+1}\\
		\hdots\\
		\a1_{n1}&\a1_{n2} & \a1_{n3} & \ldots & \a1_{nn}\vline&\a1_{nn+1}
	\end{bmatrix} \longrightarrow  \\
	&
	\longrightarrow 
	\A2=
	\begin{bmatrix}
		\a2_{11}&\a2_{12} & \a2_{13} & \ldots & \a2_{1n}\vline&\a2_{1n+1}\\
		0&\a2_{22} & \a2_{23} & \ldots & \a2_{2n}\vline&\a2_{2n+1}\\
		0&\a2_{32} & \a2_{33} & \ldots & \a2_{3n}\vline&\a2_{3n+1}\\
		\hdots\\
		0&\a2_{n2} & \a2_{n3} & \ldots & \a2_{nn}\vline&\a2_{nn+1}
	\end{bmatrix} \longrightarrow \\
	&
	\longrightarrow 
	\A3=
	\begin{bmatrix}
		\a3_{11}&\a3_{12} & \a3_{13} & \ldots & \a3_{1n}\vline&\a3_{1n+1}\\
		0&\a2_{22}  & \a3_{23} & \ldots & \a3_{2n}\vline&\a3_{2n+1}\\
		0&0 & \a3_{33} & \ldots & \a3_{3n}\vline&\a3_{3n+1}\\
		\hdots\\
		0&0 & \a3_{n3} & \ldots & \a3_{nn}\vline&\a3_{nn+1}
	\end{bmatrix}
	\longrightarrow  \dots \longrightarrow \A n
	}
	}
	Procediamo con la dimostrazione:
	sia $\A1_i$ la riga $i$-esima di $\A1$.
	Eseguiamo le seguenti operazioni elementari\footnote{le operazioni
	elementari che non cambiano il sistema sono: scambio di righe,
	moltiplicazione di una riga per $\lambda \neq 0$, aggiungere a una
	riga una combinazione lineare di altre righe}  su $\A1$:
	\eal{
	&\A1_2 \rightarrow \A1_2-\frac{\a1_{21}}{\a1_{11}}\A1_1\\
	&\A1_3 \rightarrow \A1_3 -\frac{\a1_{31}}{\a1_{11}}\A1_1\\
	&\vdots\\
	&\A1_n \rightarrow \A1_n -\frac{\a1_{n1}}{\a1_{11}}\A1_1\\
	}
	ottieniamo cosi' $\A2$.\\
	Adesso lavoriamo su $\A2$:
	\eal{
	&\A2_3 \rightarrow \A2_3-\frac{\a2_{32}}{\a2_{22}}\A2_2\\
	&\A2_4 \rightarrow \A2_4 -\frac{\a2_{42}}{\a2_{22}}\A2_2\\
	&\vdots\\
	&\A2_n \rightarrow \A2_n -\frac{\a2_{n2}}{\a2_{22}}\A2_2\\
	}
	ottieniamo cosi' $\A3$.\\
	In generale, per ricavare $\A {k+1}$:
	\eal{
	&\A k_{k+1} \rightarrow \A k_{k+1}-\frac{\a k_{{k+1}k}}{\a k_{kk}}\A k_k\\
	&\A k_{k+2} \rightarrow \A k_{k+2} -\frac{\a k_{{k+2}k}}{\a k_{kk}}\A k_k\\
	&\vdots\\
	&\A k_n \rightarrow \A k_n -\frac{\a k_{nk}}{\a k_{kk}}\A k_k
	}
	E in forma piu' compatta:
	\eal{&
	\A {k+1}_{i} := \A k_{i} -\frac{\a k_{ik}}{\a k_{kk}}\A k_k\;\; \forall i=k+1,\dots,n
	}
	In definitiva, poiche' dobbiamo arrivare fino alla matrice completa
	$\A {n}$, ovvero con $k+1=n\=k=n-1$, l'algoritmo completo e':
	\eal{&
	\pton{\A {k+1}_{i} := \A k_{i} -\frac{\a k_{ik}}{\a k_{kk}}\A k_k\;\; \forall i=k+1,\dots,n}\;\;\forall k=1,\dots,n-1
	}
	Poiche' nella riga $\A k_{k}$ tutti gli elementi $\a k_{kj},\;j<k$
	sono gia' nulli, possiamo evitare le moltiplicazioni nulle, scrivendo
	direttamente le componenti di $\A{k+1}_{i}$:
\eal{&
\pton{
\pton{\a {k+1}_{ij} := \a k_{ij} -\frac{\a k_{ik}}{\a k_{kk}}\a k_{kj}\;\;
	\forall j=k,\dots,n+1}\;\;
	\forall i=k+1,\dots,n}\;\;\forall k=1,\dots,n-1
}
Il codice ottimizzato:
	\eal{&\forall k=1,\dots,n-1\\
&\qq \forall i=k+1,\dots,n \\
&\qq \qq m:=\frac{\a k_{ik}}{\a k_{kk}}\\
&\qq\qq \forall j=k,\dots,n+1\\
&\qq\qq\qq \a {k+1}_{ij} := \a k_{ij} -m\a k_{kj}
}
	\step{}{Calcoliamo il costo}
	\begin{prova}
		\eal{&\pqua{ \a {k+1}_{ij}}=\pqua{ \a k_{ij} -m\a k_{kj}}
		=\pqua{m\a k_{kj}}=1\\
		&I_i:=\pqua{\a {k+1}_{ij}\;\;\forall j=k,\dots,n+1}=
		\sum_{j=k}^{n+1}\pqua{\a {k+1}_{ij}}=n+1-k+1=n-k+2\\
		&I_i':=\pqua{m:=\frac{\a k_{ik}}{\a k_{kk}}}+K_i
		=1+K_i=n-k+3\\
		&K_k=
		\sum_{i=k+1}^nI_i'=
		\sum_{i=k+1}^nn-k+3=(n-k+3)(n-k)\\
		&K=\sum_{k=1}^{n-1}K_k
		=\sum_{k=1}^{n-1}(n-k+3)(n-k) \ubrace{=}{l=n-k} 
		=\sum_{l=1}^{n-1}(l+3)l=3\sum_{l=1}^{n-1}l+\sum_{l=1}^{n-1}l^2=\\
		&
		\ubrace{=}{\see{sommapriminnumeri},\see{sommaquadrati}}
		3\frac{(n-1)n}{2}+\frac{2(n-1)^3+3(n-1)^2+n-1}{6}
		}
	\end{prova}
\end{proof}
	\def\A#1{A^{\mathbf{#1}}}
	\def\a#1{a^{\mathbf{#1}}}
\begin{prop}
	\label{condizionegaussnaive}
Ponendoci nel contesto della prop \see{gaussnaive}, si ha
	\eal{&\exists k:\;\a k_{kk}=0\= \exists k:\;\det D_k=0}
	dove $D_k$ e' il minore principale di $A$ di ordine $k$.\\
	Equivalentemente:
	\eal{&\forall k=1,\dots,n \;\;\a k_{kk} \neq 0\= \forall k=1,\dots,n
	\;\; \det D_k \neq 0}
	Esempi in cui si verificano queste condizioni sono:
	\eal{
	&A\T{ simmetrica, definita positiva, ovvero}\\
	&\qq  xA \TR x >0 \;\;\forall x \in \R^{1,n},\;\;A=\TR A\\
	&A\T{ simmetrica, definita negativa, ovvero}\\
	&\qq xA \TR x <0 \;\;\forall x \in \R^{1,n},\;\;A=\TR A\\
	&A\T{ a predominanza diagonale stretta, ovvero }\\
	&\qq |a_{ii}| > \sum_{j \neq i}|a_{ij}|\;\;\forall i=1,\dots,n
	}
\end{prop}
	\def\D#1{D^{\mathbf{#1}}}
\begin{proof}
	\begin{pnecessaria}
		Supponiamo che $\a h_{hh}=0$ sia il primo di quelli nulli,
		ovvero, supponiamo che
		\eal{&\a i_{ii}  \neq 0\;\;\forall i=1,\dots,h-1
		}
		Possiamo allora applicare l'algoritmo \see{gaussnaive} fino al
		passo $h$:
		\eal{&
\pton{\A {k+1}_{i} := \A k_{i} -\frac{\a k_{ik}}{\a k_{kk}}\A k_k\;\; \forall
i=k+1,\dots,n}\;\;\forall k=1,\dots,h-1 }
Poiche' ogni nuova matrice e' ottenuta aggiungendo alle righe della
precedente dei multipli di altre sue righe, per le proprieta' del
determinante, si ha
\eal{&\det \D {h}_k = \det \D 1_k = \det D_k \;\;\forall k=1,\dots,n
}
dove con $\D h_k$ intendiamo il minore principale di ordine $k$ della matrice
$\A h$.\\
Ma $\D h_h$ e' una matrice triangolare, e quindi il suo determinante e' 
\eal{&\D h_h = \a h_{11}\a h_{22} \dots \a h_{hh}  \ubrace{=}{\a h_{hh}=0} 0
}
	\end{pnecessaria}
	\begin{psufficiente}
		Sia $\det D_h=0$, e 
		\eal{&\det D_i \neq0\;\;\forall i=1,\dots,h-1}
		Se $\exists i<h:\;\a i_{ii}=0$, allora non abbiamo nulla da
		dimostrare. Supponiamo allora che
		 \eal{&\a i_{ii}  \neq 0\;\;\forall i=1,\dots,h-1\;\;(1)
		                 }
		Procedendo come nel passo precedente, si ha:
		\eal{&
		\a h_{11}\a h_{22} \dots \a h_{hh} = \det \D h_h = \det D_h = 0
		\ubrace{\>}{(1)}\a h_{hh}=0 
		}
	\end{psufficiente}
	\step{}{Esempi}
	\begin{prova}
		Se $A$ simmetrica e' definita positiva, per la
		caratterizzazione \GII{carattdefinitaposdefinitaneg}, si ha
		\eal{&D_1,D_2, \dots, D_n > 0}
		se invece e' definita negativa si ha
		\eal{&D_1 <0, D_2 >0 ,D_3<0 ,\dots}
		In entrambi i casi, nessun minore e' nullo.
	\end{prova}
\end{proof}
\begin{prop}
	\def\D{{\Delta}}
	Sia $A\in \R^{n\*n},\;\;|A| \neq 0$, $\mu(A)=\norm{\inv A}\norm A$.
	Considerando il sistema lineare
	\eal{&Ax=b}
	e il sistema perturbato da un errore
	\eal{&A(x+\D x)= b+\D b}
	si ha
	\eal{&\frac{\norm{\D x}}{\norm x}\le \mu(A)\frac{\norm{\D b}}{\norm{b}}}
	Ovvero, l'errore relativo sul risultato  e' limitato dall'errore
	relativo sui termini noti, per un fattore di $\mu(A)$.
	$\mu(A)$ viene chiamato \iemph{numero di condizionamento} di $A$\\
	Usando la norma $2$, si ha
	\def\nd#1{{\norm{#1}_{2}}}
	\eal{&\mu(A)=
	\frac{\sqrt{\lambda_M(\TR AA)}}{\sqrt{\lambda_m(\TR A A)}}\\
	&A=\TR A \> \mu(A)=\frac{|\lambda_M|}{|\lambda_m|}
	}
\end{prop}
\begin{proof}
	\def\D{{\Delta}}
	\def\nd#1{{\norm{#1}_{2}}}
	\step{}{Dim $1.$}
	\begin{prova}
	Osserviamo che
	\eal{&b=Ax \> \norm{b} =\norm {Ax} \ubrace{\le
}{\see{normamatricesubmoltiplicativita}} \norm A \norm x \>
\frac{\norm{b}}{\norm x} \le \norm A\;\;(1) \\
&A(x+\D x)= b+\D b \= Ax+A\D x = b + \D b \= A \D x = \D b \= \D x =\inv A
\D b\\
&\norm{\D x } =\norm{\inv A\D b } \ubrace{\le
}{\see{normamatricesubmoltiplicativita}} \norm{\inv A} \norm {\D b } \= 
\frac{\norm{\D x}}{\norm x} \le  {\norm{\inv A}}\frac{\norm{\D
b}}{\norm x}  = {\norm{\inv A}}\frac{\norm{\D
b}}{\norm {b}} \frac{\norm{b}}{\norm x} \le \\
& \ubrace{\le}{(1)} \norm {\inv A}\norm
A \frac{\norm{\D
b}}{\norm {b}}  = \mu(A) \frac{\norm{\D
b}}{\norm {b}} 
	}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
		Poiche' $\mu_2(A)=\nd A\nd {\inv A}$, basta usare le prop
		\see{normadueinversa}, \see{normadueinversasimmetrica}.
	\end{prova}
\end{proof}
\subsection{Fattorizzazione LU}
\begin{thm}\label{fattLU}
	Data $A\in \R^{n\*n}$, si ha
	\eal{&D_k \neq 0\;\;\forall k=1,\dots,n \> 
	A=LU\\
	&\T{dove }L,U\T{ sono le seguenti matrici triangolari }:\\
	&L=\begin{bmatrix}
	1\\
	m_{21}&1\\
	m_{31}&m_{32}&1\\
	\ldots\\
	m_{n1}&m_{n2}&\ldots & m_{n,{n-1}}1
\end{bmatrix},\;\;U=\begin{bmatrix}
	a_{11} & a_{12} & a_{13} &\ldots & a_{1n}\\
	0 & \a 2_{22} & a_{23} & \ldots & \a 2_{2n}\\
	0 & 0 &\a 3_{33} & \ldots & \a 3_{3n}\\
	\ldots\\
	0&0&0&\ldots & \a n_{nn}
\end{bmatrix}
	}
	Dove $m_{ij}, \a k_{ij}$ sono ottenuti tramite l'algoritmo
	\see{gaussnaive}.
\end{thm}
\begin{proof}
Per la prop \see{condizionegaussnaive}, la condizione $D_k \neq 0\;\;\forall
k=1,\dots,n$ assicura che e' possibile utilizzare l'algoritmo
\see{gaussnaive}, ovvero
\eal{&\a k_{kk} \neq 0\;\;\forall k=1,\dots,n}
Sia
\def\m{{\underline{m}}}
\eal{&\m_i=
\begin{pmatrix}
0&0&\ldots&\ubrace{0}{\T{posto $i$-esimo}}& m_{i+1,i} &
m_{i+2,i}&\ldots&m_{n,i}
\end{pmatrix}\\
&\m_{ij}=(\m_i)_j=\sist{0 & j\le i\\
m_{ji} & j > i}\;\;(1)\\
&M_i=I-\TR \m_ie_i
}
con $\pgra{e_i}$ base canonica di $\rn$.
\step{passoM}{Si ha 
\eal{&(M_h)_{ij}=\sist{1 & i=j\\
-m_{ji} & i > h, j=h\\
0&\T{altrimenti}}
}
Ovvero, $M_h$ e' la matrice triangolare che ha tutti $1$ nella diagonale
principale, come colonna $h$ ha $-\TR \m_i$, tutti gli altri elementi sono $0$:
\eal{&M_h=
\begin{bmatrix}
1\\
0&1\\
\vdots\\
0&0 &\ldots&0 & 1 &\\
0&0 &\ldots&0 &-m_{k+1,k} \\
0&0 &\ldots&0 &-m_{k+2,k} \\
\vdots\\
0&0 &\ldots&0 &\ubrace{-m_{n,k }}{\T{colonna k}}& & & 1
\end{bmatrix}
}
\lineapiccola\\
}
\begin{prova}
	Osserviamo che poiche' $\TR \m_h\in \R^{n\*1}$, $e_h\in \R^{1\*n}$, si
	ha $\TR \m_he_h  \in \R ^{n\*n}$. Ed e' 
	\eal{&
	(\TR \m_he_h)_{ij} = \TR \m_{hi}e_{hj} = \TR \m_{hi}\delta_{hj}
	\ubrace{=}{(1)}  \sist{0 & i\le h\\
	m_{ih}\delta_{hj}   & i > h
	}=\sist{
	m_{ih} & i> h,\;j=h\\
	0&\T{altrimenti}}
	}
	\eal{&(M_h)_{ij}=(I-\TR \m_he_h)_{ij}=\delta_{ij} - \sist{
        m_{ih} & i> h,\;j=h\\
	0&\T{altrimenti}} = \sist{1  & i=j\\
	-m_{ih} & i> h,\;j=h\\
	0&\T{altrimenti}
	}
	}	
\end{prova}
\step{passoM1A}{Si ha $M_{h-1}\dots M_1A=\D h_{n}$\\
Dove $\D h_k$ e' il minore principale di ordine $k$ di $\A h$.}
\begin{prova}
Consideriamo $M_1 A$
\eal{
&(M_1A)_{ij}=\sumrn (M_1)_{ir}A_{rj}  \ubrace{=}{\sref{passoM}} 
\sumrn 
\sist{A_{rj} & i=r\\
-m_{ri}A_{rj} & i > 1, r=1\\
0&\T{altrimenti}}\\
&M_1A=
\begin{bmatrix}
1\\
-m_{21} &1\\
-m_{31} &0&1\\
\vdots\\
-m_{n1 }&&& &1
\end{bmatrix} 
\begin{bmatrix}
	a_{11}&\ldots & a_{1n}\\
	a_{21}&\ldots & a_{2n}\\
	\vdots\\
	a_{n1}&\ldots & a_{nn}
\end{bmatrix}
=\begin{bmatrix}
	a_{11}&\ldots & a_{1n}\\
	a_{21}-m_{21}a_{11} & \ldots & a_{2n}-m_{21}a_{1n}\\
	a_{31}-m_{31}a_{11} & \ldots & a_{3n}-m_{31}a_{1n}\\
	\vdots \\
	a_{n1}-m_{n1}a_{11} & \ldots & a_{nn}-m_{n1}a_{1n}\\
\end{bmatrix}
}
E ricordando che $m_{ij}$ e' il moltiplicatore di posto $i,j$ si ha
\eal{&M_1 A =
\begin{bmatrix}
	a_{11}&a_{12} & \ldots & a_{1n}\\
	0 & a_{22}-m_{21}a_{12}& \ldots & a_{2n}-m_{21}a_{1n}\\
	\vdots\\
	0 & a_{n2}-m_{n1}a_{12}& \ldots & a_{nn}-m_{n1}a_{1n}
\end{bmatrix}=
	\begin{bmatrix}
		\a2_{11}&\a2_{12} & \a2_{13} & \ldots & \a2_{1n}\\
		0&\a2_{22} & \a2_{23} & \ldots & \a2_{2n}\\
		0&\a2_{32} & \a2_{33} & \ldots & \a2_{3n}\\
		\hdots\\
		0&\a2_{n2} & \a2_{n3} & \ldots & \a2_{nn}
	\end{bmatrix} = \D 2_n
}
Cosi' procedendo si arriva a 
\eal{&M_{h-1}\dots M_1A=\D h_{n}
}
\end{prova}
Sia $N=M_{n-1}\dots M_1$, Sia $U=NA$. Si ha
\eal{&U \ubrace{=}{\sref{passoM1A}} \D n_n
}
$\D n_n$ e' il minore di ordine $n$ dell'ultima matrice data
dall'algoritmo \see{gaussnaive}. Quindi, $U$ coincide con l'$U$ della tesi.
\step{}{$\exists \inv N$}
\begin{prova}
Abbiamo gia' visto che $M_i$ e' una matrice triangolare. Poiche' gli elementi
della sua diagonale sono tutti $1$, si ha
\eal{&|M_i|= 1 \> \exists \inv {M_i}\;\;\forall i=1,\dots,n\\
&\inv{N} = \inv {M_1}\inv {M_2} \dots \inv {M_{n-1}}
	}
\end{prova}
Sia $L=\inv N$, si ha
\eal{&U=NA \> A=\inv N U = LU
}
\step{}{Resta da controllare che $L$ sia proprio quello della tesi}
\begin{prova}
	\step{}{$\inv M_{i} = I+\TR \m_ie_i$}
	\begin{prova}
	Infatti,
	\eal{&M_i(I+\TR \m_ie_i) = (I-\TR \m_ie_i)(I+\TR \m_ie_i) 
	=I-\TR \m_ie_i\TR \m_ie_i=\\
	&\qq e_i\TR \m_i = e_i\. \m_i = \m_{ii}  \ubrace{=}{(1)}  0\\
	&=I\\
	&(I+\TR \m_ie_i) M_i=I}
	\end{prova}
	\step{}{$L=I+\sum_{i=1}^{n-1} \TR \m_ie_i$}
	\begin{prova}
		\eal{&L=\inv N=\inv {M_1}\inv {M_2} \dots \inv {M_{n-1}}
	=(I+\TR \m_1e_1)(I+\TR \m_2e_2) \dots(I+\TR \m_{n-1}e_{n-1})\\
	&(I+\TR \m_1e_1)(I+\TR \m_2e_2) =
	I+\TR \m_1e_1+\TR \m_2e_2+\TR \m_1e_1\TR \m_2e_2=\\
	&\qq e_1\TR \m_2= e_1 \. \m_2 = \m_{21}  \ubrace{=}{(1)} 0\\
	&=I+\TR \m_1e_1+\TR \m_2e_2\\
	&(I+\TR \m_1e_1+ \dots  + \TR \m_{n-2}e_{n-2})(I+\TR
	\m_{n-1}e_{n-1})=
	I+\sum_{i=1}^{n-1}\TR \m_{i}e_{i}
	+\sum_{i=1}^{n-2} \TR \m_ie_i\TR\m_{n-1}e_{n-1}= \\
	&\qq e_i\TR\m_{n-1} = e_i \. \m_{n-1} = \m_{n-1,i}  \ubrace{=}{n-1 \ge
	i,\;\;(1)} =0 \\
	&= I+\sum_{i=1}^{n-1}\TR \m_{i}e_{i}
	}
	\end{prova}
	\qedstep
	\begin{prova}
	E considerando che le matrici $\TR \m_ie_i$ sono del tipo:
	\eal{&\TR \m_ie_i=
\begin{bmatrix}
0\\
0&0\\
\vdots\\
0&0 &\ldots&0 & 0 &\\
0&0 &\ldots&0 &m_{i+1,i} \\
0&0 &\ldots&0 &m_{i+2,i} \\
\vdots\\
0&0 &\ldots&0 &\ubrace{m_{ni }}{\T{colonna i}}& & & 0
\end{bmatrix}
	}
	si ha che $L=I+\sum_{i=1}^{n-1}\TR \m_{i}e_{i}$ coincide con l'$L$
	della tesi.
	\end{prova}
\end{prova}
\end{proof}
\begin{prop}\label{gausscompleto}
	Poniamoci nel contesto della prop \see{gaussnaive}, senza supporre che
	 $\a k_{kk} \neq 0\;\;\forall
	 k=1,\dots,n-1$.\\
	Sia $s:=(1,2,\dots,n)$, inizializzato all'inizio dell'algoritmo.\\
	Definiamo le seguenti procedure:
	\eal{
	&\Let \oname{scambio\_righe} i,i':\\
	&\qq \sist{T:=a_{ij}\\
	a_{ij}:=a_{i'j}\\
	 a_{i'j}:=T}\;\;\forall j:=1,\dots,n\\
	&\Let \oname{scambio\_colonne} j,j':\\
	&\qq \sist {T:=a_{ij}\\a_{ij}:=a_{ij'}\\a_{ij'}:=T}\;\;\forall j:=1,\dots,n\\
	&\qq \sist{t:=s_j\\s_{j}:=s_{j'}\\s_{j'}:=t}\\
	&\Let \oname{pivot\_riga} k:\\
	&\qq \Let \ove i \T{ tale che  }\;\;|a_{\ove i k}|:=\max_{i:=k,\dots,n}|a_{ik}|\\
	&\qq \oname{scambio\_righe} \ove i, k\\
	&\Let \oname{pivot\_colonna} k:\\
	&\qq \Let \ove j \T{ tale che  }\;\;|a_{k\ove j}|:=\max_{j:=k,\dots,n}|a_{kj}|\\
	&\qq \oname{scambio\_colonne} \ove j, k\\
	&\Let \oname{pivot\_rigcol} k:\\
	&\qq \oname{pivot\_riga} k\\
	&\qq \oname{pivot\_colonna} k\\
	&\Let \oname{pivot\_scalato} k:\\
	&\qq d_i:=\frac{|a_{ik}|}{\max_{j=1,\dots,n}|a_{ij}|}\;\;\forall
	i=k,\dots,n\\
	&\qq \Let \ove i \T{ tale che  }\;d_{\ove i}=\max_{i=k,\dots,n}d_i\\
	&\qq \oname{scambio\_riga} \ove i, k\\
	&\Let \oname{ripristina\_colonne}:\\
	&\qq\sist{ \Se i \neq s_i:\\
	 \;\;\oname{scambio\_colonna} i,s_i}\;\;\forall i=1,\dots,n
	}
	L'algoritmo di eliminazione di Gauss generale, e' il seguente:
	\eal{
	&s:=(1,2,\dots,n)\\
	&\forall k=1,\dots,n-1\\
	&\qq \oname{pivot} k\\
&\qq \forall i=k+1,\dots,n \\
&\qq \qq m:=\frac{\a k_{ik}}{\a k_{kk}}\\
&\qq\qq \forall j=k,\dots,n+1\\
&\qq\qq\qq \a {k+1}_{ij} := \a k_{ij} -m\a k_{kj}\\
&\Se \oname{pivot} = \oname{pivot\_colonna} \; \|
\;\oname{pivot}=\oname{pivot\_rigcol}:\\
&\qq \oname{ripristina\_colonne}
}
Nota: $\oname{pivot}$ puo' essere una qualsiasi delle procedure di pivot sopra
definite.\\
Infine, l'algoritmo che permette di usare una sola matrice in memoria, e
nessuna variabile ausiliaria per i moltiplicatori, durante
tutto il corso dell'esecuzione e':
	\eal{&s:=(1,2,\dots,n)\\
	&\forall k=1,\dots,n-1\\
	&\qq \oname{pivot} k\\
&\qq \forall i=k+1,\dots,n \\
&\qq \qq a_{ik}:=\frac{a_{ik}}{a_{kk}}\\
&\qq\qq \forall j=k+1,\dots,n+1\\
&\qq\qq\qq a_{ij} := a_{ij} -a_{ik}a_{kj}\\
&\Se \oname{pivot} = \oname{pivot\_colonna} \; \|
\;\oname{pivot}=\oname{pivot\_rigcol}:\\
&\qq \oname{ripristina\_colonne}
}
\end{prop}
\begin{proof}
Per costruzione. la scelta dei vari pivot ($\ove i$, $\ove j$), permette di scambiare gli $\a
k_{kk}=0$ con altri coefficienti non nulli. Questo avviene tramite lo scambio
di righe e/o colonne. Ovviamente, lo scambio di righe o colonne effettuato da $\oname{pivot}$ non altera il
sistema.\\
Queste tecniche di pivoting, permettono anche di evitare di incorrere 
nella situazione in cui il moltiplicatore $m$ diventa molto grande. In questo
caso nella differenza
\eal{&a_{ij} := a_{ij} -ma_{kj}\;\;(1)}
si avrebbe una perdita sostanziale di cifre significative.\\
I pivot $\oname{pivot\_rigcol}, \oname{pivot\_scalato}$ permettono anche di
evitare la situazione in cui nella $(1)$, $ a_{ij} $ e' molto piu' piccolo
rispetto a $a_{kj}$.\\
Infine, l'algoritmo ottimizzato per la memoria usa la cella della matrice che
sara' sovrascritta da uno zero per memorizzare il moltiplicatore, e inoltre, sfrutta il fatto che $\a k_{ij}=\a
{k+1}_{ij}=\dots=\a n_{ij}$.
\end{proof}
\begin{thm}\label{fattPALU}
	Data $A\in \R^{n\*n},\;|A| \neq 0$, si ha
	\eal{&\exists P\T{ matrice di permutazione: } PA=LU}
	dove $L,U$ sono le matrici triangolari descritte nel
	thm \see{fattLU}, che si ottengono pero'
 usando l'algoritmo \see{gausscompleto} con un pivot che non
	scambia colonne.\\
Nota: e' essenziale usare la versione dell'algoritmo che salva i
	moltiplicatori nella stessa matrice $A$, infatti, anche le righe di
	$L$ devono essere scambiate durante l'esecuzione.\\

Una matrice $P$, si dice matrice di permutazione se e' ottenuta dalla matrice
identica $I$, mediante scambi di righe (o, equivalentemente, di colonne).
\end{thm}
\begin{proof}
Ricordiamo che $PA$ e' quella matrice ottenuta da $A$ effettuando lo stesso
scambio di righe che sono state utilizzate per ottenere $P$ da $I$ (vedi \AL{matidentproprieta}).\\
Rileggendo l'algoritmo \see{gausscompleto}, possiamo esprimere lo scambio di
righe (o di colonne) di $A$ mediante una opportuna matrice di permutazione
$P_i$. I passi compiuti dall'algoritmo si possono allora esprimere cosi':
\eal{
&M_1P_1Ax=M_1P_1b\\
&M_2P_2M_1P_1 Ax=M_2P_2M_1P_1 b\\
&\dots\\
&M_{n-1}P_{n-1}\dots M_2P_2M_1P_1 Ax=M_{n-1}P_{n-1}M_2P_2M_1P_1 b\\
}
Consideriamo la matrice $M_{n-1}P_{n-1}\dots M_2P_2M_1P_1 A$ e poniamo
$P=P_{n-1}P_{n-2}\dots P_1$. Esaminiamo solo il caso $n=4$.
\eal{&U = (M_{3}P_{3})(M_2P_2)(M_1P_1)A  \ubrace{=}{P_iP_i=I}
(M_3P_3)(M_2P_3P_3P_2)(M_1P_2P_3P_3P_2P_1)A = \NN
=
M_3 (P_3M_2P_3)(P_3P_2M_1P_2P_3)(P_3P_2P_1)A  = \inv L P A \=
PA = LU
}

\end{proof}

\subsubsection{Applicazioni}
\begin{prop}
	Data la matrice $A\in \R^{n\*n},\;|A| \neq 0$, e la matrice $U$
	ottenuta dalla fattorizzazione \see{fattPALU}, si ha
	\eal{&\det A =(-1)^s\prod_{i=1}^{n}u_{ii} }
dove $s$ e' il numero di scambi di righe effettuati durante la
fattorizzazione
\see{fattPALU}
,
o equivalentemente $(-1)^{s} = \det P$
\\
	Il costo di questo calcolo e' quindi
	\eal{&\T{costo di }\see{fattPALU} + n-1 \approx \frac{n^3}{3}+O(n^2)
	}
\end{prop}
\begin{proof}
Si ha
\eal{&\det PA = \det P \det A  = \det P \det A\\
&\det PA =\det LU  = \det L \det U= \det U  \ubrace{=}{U\T{ e' triangolare}}
\prod_{i=1}^{n}u_{ii}\\
&\det P \det A = \prod_{i=1}^{n}u_{ii}
}
Ricordando che uno scambio di riga cambia di segno il determinante, si ha
\eal{&\det P = (-1)^{s}\det I = (-1)^s\\
&\det A = (-1)^s \prod_{i=1}^{n}u_{ii}
}
dove $s$ e' il numero di righe che sono state scambiate per ottenere $P$ da
$I$.
Ma dato che  $P=P_{n-1}\dots P_1$, $s$ si puo' conoscere direttamente
considerando il numero di scambi di righe effettuati durante l'uso
dell'algoritmo \see{fattPALU}.
\end{proof}
\begin{prop}\label{multisistemi}
	Sia $A\in \R^{n\*n},\;\;|A| \neq 0$.
Siano dati $m$ sistemi lineari del tipo:
\eal{&Ax_k=b_k\;\;k=1,\dots,m}
Per risolverli si puo' procedere cosi':
\eal{&\T{ Si fattorizza $A$ in }PA=LU\\
&\forall k=1,\dots,m\\
&\qq y:=Ux_k\\
&\qq \ove b_k=Pb_k\\
&\qq \T{Si risolve con \see{propsoluztriang} il sistema triangolare }Ly=\ove b_k\\
&\qq \T{Si risolve con \see{propsoluztriang} il sistema triangolare }Ux_k=y
}
Il costo di questo algoritmo e' 
\eal{&\frac{n^3}{3}+mn^2 + O(n) }
\end{prop}
\begin{proof}
	Fissiamo $k$
\eal{&Ax_k=b_k\\
&PAx_k=Pb_k\\
&LUx_k=Pb_k=\ove b_k\\
&\qq \T{Sia }y=Ux_k\\
&Ly=\ove b_k
}
Il costo dell'algoritmo \see{propsoluztriang} usato per risolvere il sistema
triangolare e' $\frac{n^2}{2}+O(n)$. Poiche' stiamo risolvendo due sistemi
triangolari, abbiamo $n^2+O(n)$.
\end{proof}
\begin{prop}
Sia $A\in \R^{n\*n},\;\;|A| \neq 0$. Sia $C=\inv A$.\\
Per calcolare $C$ si puo' procedere cosi':
\eal{&\forall i=1,\dots,n\\
&\qq \T{Si risolve con \see{multisistemi} il sistema }AC^i=e_i
}
dove $C^i$ e' la colonna $i$-esima di $C$.\\
Il costo e' 
\eal{&\frac{4}{3}n^3 + O(n) }
\end{prop}
\begin{proof}
$AC=A\inv A = I$, e poiche' $AC^i=I^i$, si deve avere
	\eal{&AC^i=e_i\;\;\forall i=1,\dots,n}
	Applicando la \see{multisistemi}, con $m=n$, si ricava il costo
	dell'algoritmo.
\end{proof}
\subsection{Fattorizzazione di Cholesky}
\begin{thm}
	Sia $A\in \R^{n\*n}$ una matrice simmetrica e definita positiva,
	allora
	\eal{&\exists R\in \R^{n\*n}\T{ triangolare inferiore: }A=R\TR R}
L'algoritmo per ricavare $R$ e':
	\eal{&\forall j=1,\dots,n\\
	&\qq r_{jj}:=\sqrt{a_{jj}-\sum_{k=1}^{j-1}r_{jk}^2 }\\
	&\qq \forall i=j+1,\dots,n\\
	&\qq\qq r_{ij} := \frac{a_{ij} - \sum_{k=1}^{j-1}r_{ik}r_{jk} }{r_{jj}}
	}
\end{thm}
\begin{proof}
	La condizione $A=R\TR R$ si traduce nel sistema
	\eal{
	&a_{ij}= \sum_{k=1}^{n}R_{ik}(\TR R)_{kj}\;\;\forall j=1,\dots,n,\;\;\forall i=1,\dots,n\=\\
	&\= a_{ij}= \sum_{k=1}^{n}R_{ik}R_{jk}\;\;\forall j=1,\dots,n,\;\;\forall i=1,\dots,n
	}
	dove $r_{hk}$ sono gli elementi di $R$ e le incognite del sistema
	\footnote{Sfruttando le ipotesi fatte su $A$, si puo' dimostrare per via teorica che tale sistema ammette
	soluzione}.\\
	Tenendo conto del fatto che $R$ e' una matrice triangolare inferiore,
	possiamo scrivere
	\eal{
	&a_{ij}= \sum_{k=1}^{\min\pgra{i,j}}R_{ik}(\TR R)_{kj}
	\;\;\forall j=1,\dots,n,\;\;\forall i=1,\dots,n
	}
	Poiche' $A$ e' simmetrica,  $a_{ij}=a_{ji}$, quindi le uniche
	equazioni che ci interessano sono:
	\eal{
	&a_{ij}= \sum_{k=1}^{\min\pgra{i,j}}r_{ik}r_{jk}\;\;
	\forall j=1,\dots,i,\;\;\forall i=1,\dots,n
	}
	Adesso basta scrivere le equazioni nel seguente ordine:
	\eal{&
	\sist{1.\;\;a_{11}=r_{11}^2\\
	2.\;\;a_{i1} = r_{i1}r_{11}\;\;\forall i=2,\dots,n\\
	3.\;\;a_{22}= r_{21}^2+r_{22}^2\\
	4.\;\;a_{i2}=r_{i1}r_{21}+r_{i2}r_{22}\;\;\forall i=3,\dots,n\\
	\vdots
	}
	}
	e ricavare le equazioni dall'alto verso il basso.
	Per ricordare l'ordine delle equazioni si puo' usare questo disegno:
	\eal{&
	\begin{bmatrix}
		1.\\
		2.&3.\\
		2.&4.&5.\\
		2.&4.&6.
	\end{bmatrix}
	}
	Le incognite sono:
	\eal{&r_{11}=\sqrt{a_{11}}\\
	&r_{i1} = \frac{a_{i1}}{r_{11}}\;\;\forall i=2,\dots,n\\
	&r_{22}= \sqrt{a_{22}-r_{21}^2}\\
	&r_{i2} = \frac{a_{i2} - r_{i1}r_{21}}{r_{22}}\;\;\forall
	i=3,\dots,n\\
	&\dots
	}
	Le radici quadrate sono lecite perche' $A$ e' definita positiva.\\
	In generale,
	\eal{&a_{jj}= \sum_{k=1}^{j}r_{jk}^2  = r_{jj}^2 +
	\sum_{k=1}^{j-1}r_{jk}^2  \=
	r_{jj}=\sqrt{a_{jj}-\sum_{k=1}^{j-1}r_{jk}^2 }\\
	&a_{ij} = 
	\sum_{k=1}^{j}r_{ik}r_{jk} = r_{ij}r_{jj} +
	\sum_{k=1}^{j-1}r_{ik}r_{jk} \= 
	= r_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1}r_{ik}r_{jk} }{r_{jj}}\;\;\forall i=j+1,\dots,n
	}
	L'algoritmo completo e' quindi
	\eal{&\forall j=1,\dots,n\\
	&\qq r_{jj}:=\sqrt{a_{jj}-\sum_{k=1}^{j-1}r_{jk}^2 }\\
	&\qq \forall i=j+1,\dots,n\\
	&\qq\qq r_{ij} := \frac{a_{ij} - \sum_{k=1}^{j-1}r_{ik}r_{jk} }{r_{jj}}
	}
\end{proof}
\subsection{Autovalori}
\def\S{{\Sigma}}
\def\s{{\sigma}}
\begin{thm}
	\label{SVD}
	\label{USV}
	Data $A\in \R^{m\*n}$, con $m\ge n$, 
	\eal{&\exists U\in \R^{m\*m},
	\S\in \R^{m\*n},\;V\in \R^{n\*n}\T{ ortogonali, tali che }
	A=U\S \TR V\\
	&
	\S=\begin{bmatrix}
	\s_1\\
	&\s_2\\
	& &\s_3\\
	\dots\\
	&   &   &      & \s_n\\
      0 & 0 & 0 & \ldots & 0\\
      0 & 0 & 0 & \ldots & 0\\
      \vdots\\
      0 & 0 & 0 & \ldots & 0\\
	\end{bmatrix}\\
	&\s_1\ge \s_2\ge \dots \ge  \s_n \ge 0
	}
	I $\s_i$ si chiamano \emph{valori singolari}.
\end{thm}
\begin{prop}
	Nel contesto del thm \see{SVD}, se $r$ e' il rango di $A$, allora
	\eal{&A=\sum_{i=1}^r \s_iU^i\TR V^i}
	dove $U^i$ e' la colonna $i$-esima di $U$, $V^i$ la colonna $i$-esima
	di $V$.
	Inoltre,
	\eal{&\s_1=\norm{A}_2}
\end{prop}
\begin{proof}
	Per il thm \see{SVD}
	\eal{&A=U\S \TR V = \sum_{i=1}^n \s_iU_i\TR V^i	}
	Si ha
	\eal{&
	\s_h \neq 0  \ubrace{\>}{\s_1 \ge \s_2 \ge \dots \ge  \s_n \ge 0 }
	\s_1,\dots, \s_h  \neq 0
	}
%Il rango di $A$ e' uguale al rango di $\S$. Che e' il numero di $\s_i$ non
%nulle.
\end{proof}
\def\l{{\lambda}}
\begin{thm}
	di Gershgorin-Hadamard.
	Sia $A\in C^{n\*n}$, e siano
	\eal{&D_i=\pgra{z\in \C\;|\;|z-a_{ii}|\le R_i}\;\;\qq\T{ [e' un cerchio
	in $\C$ di centro $a_{ii}$, raggio  $R_i$]}\\
	&R_i= \sum_{j \neq i}|a_{ij}|\\
	&D=\bigcup_{i=1}^nD_i}
	Si ha:
	\eal{&\l\T{ autovalore di }A\>\l \in D}
\end{thm}
\begin{proof}
	Sia $u\in \C^{n\*1}$ l'autovettore di $A$, associato a $\l$. Si ha
	\eal{&u_k\T{ autovettore } \> u_k \neq 0\\
	&Au=\l u \= \sum a_{ij}u_{j} = \l u_i \= 
	a_{ii}u_i+
	\sum_{j \neq i}
	a_{ij}u_j = \l u_i \= 
	   \sum_{j \neq i}
	   a_{ij}u_j = (\l-a_{ii})u_{i}\\
	&|\sum_{j \neq i}
	   a_{ij}u_j| = 
	   |(\l-a_{ii})u_{i} | =
	   |\l-a_{ii} | |u_i|\\
	 & |\l-a_{ii} | |u_i| = |\sum_{j \neq i}
	 a_{ij}u_j| \le \sum_{j \neq i}|a_{ij}| |u_j|\;\;(1)
	}
	Sia $k:\;|u_k|=\max\pgra{|u_i|}_{i}$. Ponendo $i=k$ nella $(1)$, si ha
	\eal{&|\l-a_{kk} | |u_k|
	\le \sum_{j \neq k}|a_{kj}| |u_j|
	\ubrace{\le}{|u_k|=\max\pgra{|u_i|}} \sum_{j \neq k}|a_{kj}| |u_k|
	= |u_k| \sum_{j \neq k}|a_{kj}| 
	\\
	&|\l-a_{kk} | |u_k|  \le  |u_k| \sum_{j \neq k}|a_{kj}|
	\ubrace{\>}{u_k \neq 0}  |\l-a_{kk} | \le   \sum_{j \neq k}|a_{kj}|
	=R_k \> \l\in D_k\( D
	}
\end{proof}
\def\s{{\sigma}}
\begin{prop}\label{metodopotenze}
	Metodo delle potenze per il calcolo dell'autovalore massimo.\\
	Siano $\l_1,\dots,\l_n$ tutti gli autovalori di $A\in \C^{n\*n}$, matrice diagonalizzabile. Sia
\eal{&x_0\in \C^{n,1},\;\;x_0 \neq 0\\
&\sist{y_k=\frac{x_k}{\norm{x_k}}\\
x_{k+1}=Ay_k} \;\;\forall k=0,1,2,\dots\\
&\s_k=\frac{\TR x_kAx_k}{\TR x_k x_k}
}
$\s(x)=\frac{\TR xAx}{\TR xx}$ e' chiamato rapporto di Rayleigh.
Supponiamo che
\eal{&|\l_1| > |\l_2| \ge |\l_3| \ge \dots \ge  |\l_n|}
Allora si ha:
\eal{&
\s_k=\frac{\TR y_kx_{k+1}}{\TR y_ky_k}\\
&\lim_{k\to \8} \s_k = \l_1\\
%&\lim_{k\to \8} y_k=u_1
}
%dove $u_1$ e' l'autovettore 
Una successione piu' semplice, ma meno stabile dal punto di vista numerico e' 
\eal{&z_0=x_0,\;z_{k+1}=Az_k,\;\s_k'=\frac{\TR z_kAz_k}{\TR z_kz_k}}
Supponendo che 
\eal{&
|\l_1| > |\l_2 | > |\l_3| >  \dots >|\l_h| > |\l_{h+1}| \ge |\l_{h+2}| \ge \dots \ge  |\l_n| 
}
per ricavare $\l_h$ poniamo
\eal{&
x_0'=x_0-\sum_{i=1}^{h-1}\alpha_iu_i
}
,dove $\alpha_i,u_i$ sono descritti nella dimostrazione, e riapplichiamo lo
stesso algoritmo. Il nuovo $\s_k$ convergera' a $\l_h$.\\

Infine, scelto un errore $\eps>0$, possiamo arrestare la successione quando
\eal{&\frac{\norm{(A-\s_kI)y_k}}{\s_k\norm {y_k}} < \eps
}
oppure quando
\eal{&|\s_{k+1}-\s_k|<\eps }
\end{prop}
\begin{proof}
	\def\l{{\lambda}}
	\def\a{{\alpha}}
		\def\x{{z}}
Sia $\x_0=x_0,\;\;\x_{k+1}=A\x_{k}$, si ha
	\eal{&
A\T{ diagonalizzabile} \> \exists B=\pgra{u_1,\dots,u_n}\T{ base di } \C^{n\*
n}:\;\;Au_i=\lambda_i u_i\;\;(1)\\
&B\T{ base }\> x_0= \sumin \a_iu_i\\
&\x_1=A\x_0=\sumin \a_i Au_i \ubrace{=}{(1)} \sumin \a_i\l_iu_i\\
&\x_2=A\x_1=\sumin \a_i\l_i Au_i \ubrace{=}{(1)} \sumin \a_i\l_i^2u_i\\
&\dots\\
&\x_k=A\x_{k-1}=\sumin \a_i\l_i^{k}u_i\;\;(1.1)
}
Con $[v]_i$ indichiamo la componente $i$-esima del vettore $v$ secondo la base
canonica. Se $\a_1u_{1l} \neq 0$, si ha
\eal{&\frac{[\x_{k+1}]_l}{[\x_k]_l}=
\frac{\sumin \a_i\l_i^{k+1}u_{il}}{\sum \a_i\l_i^ku_{il}}=
\frac{\l_1^{k+1}}{\l_1^k} \frac{\a_1u_{1l} + \sum_{i=2}^n \a_i\frac{\l_i^{k+1}}{\l_1^{k+1}}u_{il}}{
\a_1u_{1l} + \sum_{i=2}^n\a_i\frac{\l_i^{k}}{\l_1^{k}}u_{il}}=\\
&= \l_1 \frac{\a_1u_{1l} + \sum_{i=2}^n \a_i\pton{\frac{\l_i}{\l
_1}}^{k+1}u_{il}}{
\a_1u_{1l} + \sum_{i=2}^n\a_i\pton{\frac{\l_i}{\l_1}}^ku_{il}}\;\;(2)
}
Poiche' $\l_1 > \l_i$ si ha che
\eal{&\lim_{k\to \8}\pton{\frac{\l_i}{\l_1}}^k =0}
e quindi dalla $(2)$
\eal{&\lim_{k\to \8}\frac{[\x_{k+1}]_l}{[\x_k]_l}= \l_1}
Per evitare di dover scegliere ogni volta una componente opportuna, si puo'
usare $\s_k$,
\eal{&\TRC \x_k\x_k \ubrace{=}{(1.1)}  \sumin \ove{\a_i}\a_i{\ove
\l_i}^{k}\l_i^k=
\sumin |\a_i|^2|\l_i|^{2k}=
|\l_1|^{2k}\pton{|\a_1|^2+\sum_{i=2}^n
|\a_i|^2\pton{\frac{|\l_i|}{|\l_1|}}^{2k} }\;\;(3)\\
&A\x_k=\x_{k+1} \> \TRC \x_kA\x_k = \TRC \x_k\x_{k+1}  \ubrace{=}{(1.1)}
\sumin |\a_i|^2\ove \l_i^{k}
\l_i^{k+1} = \sumin |\a_i|^2|\l_i|^{2k}\l_i=\\
&\qq
=|\l_1|^{2k}\l_1\pton{|\a_1|^2+\sum_{i=2}^n
|\a_i|^2\pton{\frac{|\l_i|}{|\l_1|}}^{2k}\frac{\l_i}{\l_1} } \;\;(3.1)\\
&\s_k' = \frac{\TRC \x_kA\x_k }{\TRC \x_k\x_k} \ubrace{=}{(3),(3.1)} 
\l_1 \frac{|\a_1|^2+\sum_{i=2}^n
|\a_i|^2\pton{\frac{|\l_i|}{|\l_1|}}^{2k}\frac{\l_i}{\l_1}}{|\a_1|^2+\sum_{i=2}^n
|\a_i|^2\pton{\frac{|\l_i|}{|\l_1|}}^{2k}}  \>
\lim_{k\to \8} {\s_k'} = \l_1
}
dove con $\ove \a_i$ abbiamo indicato il complesso coniugato di $\a_i$.\\
Poiche' 
\eal{&
[\x_k]_l=\l_1^k\pton{\a_1u_{1l} +
\sum_{i=2}^n\a_i\pton{\frac{\l_i}{\l_1}}^ku_{il}} \>\\
&\> \lim_{k\to \8 } |[\x_k]_l| =\sist{+\8& |\l_1| > 1\\
|\a_iu_{il}|& \l_1=1\\
0 & 0\le |\l_1|< 1}
}
nell'implementazione macchina rischiamo di incorrere in errori di overflow o
di underflow. Lo stesso problema si riscontra in $\TRC z_kz_k$ e in $\TRC
z_kAz_k$, perche' figura $|\l_1|^{2k}$. Per questo motivo si usano gli $x_k,y_k$ della tesi, in modo
tale da avere gli $y_k$ della successione con $\norm{y_k}=1$. I calcoli svolti
fin adesso non variano, infatti, si vede facilmente che
\eal{&y_k=\frac{\x_k}{\norm{\x_k}},\T{ infatti, per induzione:}\NN
\qq y_0=\frac{x_0}{\norm{x_0}} = \frac{z_0}{\norm{z_0}} \NN
\qq x_{k+1}=Ay_k \ubrace{=}{\T{Hp induttiva}} A\frac{z_k}{\norm{z_k}}
=\frac{z_{k+1}}{\norm{z_k}}\;\;(*)\NN
\qq y_{k+1}=\frac{x_{k+1}}{\norm{x_{k+1}}}  \ubrace{=}{(*)} 
\frac{z_{k+1}}{\norm{z_k}\frac{\norm{z_{k+1}}}{\norm{z_k}}} =
\frac{z_{k+1}}{\norm{z_{k+1}}}\\
&x_{k+1}=Ay_k=\frac{\x_{k+1}}{\norm{\x_k}}\\
&\s_{k+1}
=\frac{\TR x_{k+1}Ax_{k+1}}{\TR x_{k+1} x_{k+1}}
=\frac{\frac{\TR \x_{k+1}}{\norm{\x_k}}A\frac{\x_{k+1}}{\norm{\x_k}}}
{\frac{\TR \x_{k+1}}{\norm{\x_k}}\frac{\x_{k+1}}{\norm{\x_k}}}
=\frac{\TR \x_{k+1}A\x_{k+1}}{\TR \x_{k+1}\x_{k+1}} =\s_{k+1}'
}
Stavola i calcoli sono stabili, infatti,
\eal{&\TRC y_ky_k=\frac{\TRC z_kz_k}{\norm{z_k}\norm{z_k}} =
\frac{z_k\.z_k}{\norm{z_k}^2}=1\\
&\TRC y_kAy_k=\l_1\frac{(\dots)}{(\dots)}\;\;\;\T{ [non compare piu'
$|\l_1|^{2k}$]}
}
\step{}{Dim. $\frac{\TRC y_kx_{k+1}}{\TRC y_ky_k}=\s_k$}
\begin{prova}
Infine abbiamo
\eal{&\frac{\TRC y_kx_{k+1}}{\TRC y_ky_k} 
	=\frac{\frac{\TRC x_k}{\norm{x_k}}x_{k+1}}{\frac{\TRC x_k}{\norm
	x_k}\frac{x_k}{\norm{x_k}}} = 
	\frac{\TRC x_k x_{k+1}}{\TRC x_k\frac{x_k}{\norm{x_k}}}=\\
	&
	=\frac{\TRC x_k Ay_k}{\TRC x_k\frac{x_k}{\norm{x_k}}}
	=\frac{\TRC x_k A\frac{\TRC x_k}{\norm{x_k}}}{\TRC x_k\frac{x_k}{\norm{x_k}}}
	=\frac{\TRC x_k A x_k}{\TRC x_kx_k} = \s_k
}
\end{prova}
\step{}{Calcolo di $\l_h$}
\begin{prova}
Abbiamo
\eal{&x_0'=x_0-\sum_{i=1}^{h-1}\alpha_iu_i
=
\sum_{i=h}^n\a_iu_i
}
In pratica, da $x_0$ abbiamo eliminato tutti i termini precedenti a $\a_hu_h$.
Adesso, il $\l_i$ dominante e' $\l_h$.
Ripetendo in modo analogo i ragionamenti di prima, si ha la tesi.
\end{prova}
\step{}{Criterio di arresto}
\begin{prova}
Il criterio di arresto, si basa sulle seguenti osservazioni:
\eal{&Au_1=\l_1 u_1 \= (A-\l_1I)u_1=0\\
&\lim_{k\to \8}y_k=u_1\\
&\lim_{k\to \8} \s_k=\l_1\\
&\qq \lim_{k\to \8} (A-\s_kI)y_k=\ubrace{0}{\T{vettore nullo}}\\
&\qq \lim_{k\to \8} \norm{(A-\s_kI)y_k}=0
}
\end{prova}
\end{proof}
\begin{prop}
	\label{metodopotenzeinverse}
Metodo delle potenze inverse per il calcolo dell'autovalore minimo.\\
Siano $\l_1,\dots,\l_n$ tutti gli autovalori di $A\in \C^{n\*n}$, matrice diagonalizzabile. Sia
\eal{&x_0\in \C^{n,1},\;\;x_0 \neq 0\\
&\sist{y_k=\frac{x_k}{\norm{x_k}}\\
x_{k+1}=\inv Ay_k} \;\;\forall k=0,1,2,\dots\\
&\s_k=\frac{\TR y_k\inv A y_k}{\TR y_k y_k}
}
Supponiamo che
\eal{&\exists \inv A\\
&|\l_1| \ge  |\l_2| \ge \dots \ge |\l_{n-1}|  >  |\l_n|}
Allora si ha:
\eal{
&\lim_{k\to \8} \s_k = \frac{1}{\l_n}
}
Al posto di calcolare $\inv A$, per poi calcolare i termini della successione:
\eal{&x_{k+1}=\inv Ay_k }
conviene calcolare i termini risolvendo di volta in volta il sistema
\eal{&Ax_{k+1}=y_k
}
nell'incognita $x_{k+1}$.\\
Poiche' i singoli sistemi hanno la stessa matrice dei coefficienti, si puo'
usare la prop. \see{multisistemi}.
\end{prop}
\begin{proof}
Basta osservare che
\eal{&\l_i\T{ autovalore di }A\= \frac{1}{\l_i}\T{ autovalore di }\inv A\\
&\frac{1}{|\l_1|}\le \frac{1}{|\l_2|}\le  \dots \le  \frac{1}{|\l_{n-1}|}  <
\frac{1}{|\l_n|}\\
&\lambda_{\T{max}}(\inv A)=\frac{1}{\lambda_{\T{min}}(A)}
\= \lambda_{\T{max}}(\inv A)=\frac{1}{\lambda_n}
}
(vedi la dimostrazione di \see{normadueinversa}) e applicare la prop.
\see{metodopotenze}.
\end{proof}
	\def\l{{\lambda}}
	\def\m{{\mu}}
	\def\s{{\sigma}}
\begin{prop}
	\label{raffinamentoiterativo}
	Nelle ipotesi della prop \see{metodopotenzeinverse}, preso un
 $\m_0\in \C$ e ponendo
	\eal{&A_{\m_k}=A-\m_k I\\
	&\s^{(k)}\T{ approssimazione di $\s_i$ di $A_{\m_k}$ calcolato con la prop.
	\see{metodopotenzeinverse}, con errore $\eps$ }\\
	&\m_{k+1}=\m_k+\frac{1}{\s^{(k)}}
	}
	si ha
	\eal{&\lim_{k\to \8}\m_k=\l_\m
	}
	dove $\l_\m$ e' l'autovalore di $A$ piu' vicino a $\m$, ovvero
	\eal{&|\l_\m-\m|\le |\l_i-\m|\;\;\forall i=1,\dots,n
	}
\end{prop}
\begin{proof}
	Si ha
	\eal{&\l \T{ autovalore di }A\=
	Au=\l u\= Au-\mu u = \l u -\mu u \= (A-\m I)u=(\l-\m)u \= A_\m u =
	(\l-\m)u \= \l-\m\T{ autovalore di }A_\m\\
	&\qq \> \T{Gli autovalori di }A_\m\T{ sono
	}\pgra{\l_i-\m\;|\;i=1,\dots,n}\;\;(1)
	}
	Quindi applicando la prop \see{metodopotenzeinverse} a $A_\m$, abbiamo
	che \eal{&\s^{(0)} \approx \frac{1}{\lambda_{\T{min}}(A_\m)}
	\ubrace{=}{(1)} 
	\frac{1}{\l_t-\m}\\
	&\T{ dove }  |\l_t-\m|\le |\l_i-\m|\;\;\forall i=1,\dots,n\\
	&\s^{(0)} \approx \frac{1}{\l_t-\m} \= \frac{1}{\s^{(0)} }\approx
	\l_t-\m \= \frac{1}{\s^{(0)} } +\m\approx \l_t
	}
Ponendo $\mu_1=\frac{1}{\s^{(0)} } +\m$, e reiterando,
	otteniamo 
	\eal{&\frac{1}{\s^{(1)} } +\m_1 \approx \l_t
	}
	che e' una approssimazione migliore di $\l_t$.
\end{proof}
\section{Interpolazione e approssimazione}
\begin{defn}
	Supponiamo di avere gli $n+1$ punti $(x_i,y_i)\in \rd\;\;\forall i=0,1,\dots,n$.
	L'interpolazione consiste nel trovare una funzione
	$f:\R\longrightarrow \R$ tale che
	\eal{&f(x_i)=y_i\;\;\forall i=0,1,\dots,n}
	\begin{description}
		\item[Interpolazione polinomiale] Si richiede che $f(x)$ sia
			un polinomio in $\R[x]$ di grado minimo.
		\item[Interpolazione razionale] Si richiede che $f(x)$ sia una
			funzione razionale, ovvero che si del tipo
			\eal{&\frac{g(x)}{h(x)},\;\;g(x),h(x)\in
			\R[x]}
		\item[Interpolazione trigonometrica] Si richiede che $f(x)$
			sia una funzione di periodo $L$. Si ricerca una
			soluzione tra le funzioni del tipo
			\eal{&\frac{a_0}{2}+\sum_{k=1}^n\pton{b_k\sin\pton{k\frac{2\pi}{L}x}+
	a_k\cos\pton{k\frac{
	2\pi}{L}x}}}
	\end{description}
\end{defn}
\subsection{Interpolazione polinomiale}
\begin{prop}\label{calcolopolinomio}
	Sia $f(x)=a_0+a_1x+\dots+a_nx^n$. Un algoritmo per computare $f(x)$ in
	maniera efficace e' il seguente:
	\eal{
	&t:=a_n\\
	&\forall i=1,\dots,n\\
	&\qq t:=a_{n-i}+tx
	}
	Il costo dell'algoritmo e' quindi 
	\eal{&n\T{ moltiplicazioni},\;\;n\T{ addizioni}}
\end{prop}
\begin{prop}\label{esisteunicasolinterpolpolinom}
	\eal{\exists ! p(x)\in \R[x]_n:\;\; p(x_i)=y_i\;\forall
	i=0,1,\dots,n \= x_i \neq x_j \;\;\forall i>j}
	dove $\R[x]_n$ e' lo spazio vettoriale dei polinomi di grado $\le n$ a
	coefficienti reali.
\end{prop}
\begin{proof}
	Sia $p(x)$ il generico polinomio di grado $\le n$ incognita:
	\eal{&p(x)=\sumzjn a_jx^j}
\eal{&p(x_i)=y_i\;\;\forall i=0,\dots,n\=\sumzjn a_jx_i^j=y_i\;\;\forall
i=0,\dots,n
	}
	Quest'ultimo e' un sistema lineare nelle incognite
	$a_0,\dots,a_{n}$, in $n+1$ equazioni. La matrice dei coefficienti e'
	\eal{&V=\begin{bmatrix}
		x_0^0 & x_0^1 & \ldots & x_0^n\\
		x_1^0 & x_1^1 & \ldots & x_1^n\\
		\vdots\\
		x_n^0 & x_n^1 & \ldots & x_n^n
	\end{bmatrix}}
	Il suo determinante e' il noto determinante di Vandermonde:
	\eal{&|V|=\prod_{i>j}{x_{i}-x_j}}
	Il sistema ammette un unica soluzione $ \= |V| \neq 0$, ovvero
	\eal{&|V| \neq 0\= x_{i}-x_j \neq 0\;\;\forall i>j}
\end{proof}
\begin{thm}\label{formalagrange}
	Forma di Lagrange.\\
	Sia
	\eal{&
	\l_j(x) =\prod_{0\le i\le n,\;\;i \neq j} \frac{x-x_i}{x_j-x_i}
	}
	allora la soluzione dell'interpolazione e'
	\eal{&
	p(x) =\sumzjn y_j\l_j(x)
	}
\end{thm}
\begin{proof}
	Nella dimostrazione \see{esisteunicasolinterpolpolinom}, abbiamo visto
	che trovare $p(x)$ equivale a risolvere il sistema
	\eal{&Va = y\\
	&\T{ con } a=
	\begin{bmatrix}
		a_0\\
		a_1\\
		\vdots\\
		a_n
	\end{bmatrix},\;\;y=
	\begin{bmatrix}
		y_0\\
		y_1\\
		\vdots\\
		y_n
	\end{bmatrix}
	}
	\pfsketch{
	Poiche' $p(x)\in \R[x]$ e $\R[x]_n$ e' uno spazio vettoriale, possiamo
	considerare una base $\pgra{\l_0(x),\l_1(x),\dots,\l_n(x)}$ in modo tale che
	la nuova matrice dei coefficienti $V'$ sia $I$ e che $\deg \l_j(x)\le
	n$}
	Ovvero:
	\eal{
	&p(x)=\sumzjn a_j'\l_j(x)\;\;(1)\\
	&p(x_i)=\sumzjn a_j'\l_j(x_i)\;\;\forall i=0,1,\dots,n\;\;(1.1)\\
	&(V')_{ij}=\l_j(x_i)\\
	&V=I \= (V)_{ij}=\delta_{ij}\= \l_j(x_i)=\delta_{ij}
	}
	Ricaviamoci i $\l_j(x)$:
	\eal{&\l_j(x_i)=\delta_{ij} \;\;\forall i \> \l_j(x_i) =0\;\;\forall
	i \neq j \\
	&\sist{\l_j(x_i) =0\;\;\forall i=0,1,\dots,j-1,j+1,\dots,n\\
	\deg \l_j(x) \le n}  \ubrace{\>}{\T{Ruffini}} 
	\l_j(x)=c\prod_{i \neq j} x-x_i\\
	&\l_j(x_j)=1 \= c\prod_{i \neq j} x_j-x_i=1\= c=\frac{1}{\prod_{i \neq
	j} x_j-x_i}\\
	&\qq \> 
	\l_j(x) = \frac{\prod_{i \neq j} x-x_i}{\prod_{i \neq j} x_j-x_i}
	=
	\prod_{0\le i\le n,\;\;i \neq j} \frac{x-x_i}{x_j-x_i}
	}
	Quindi
	\eal{&p(x_i)=y_i  \ubrace{\=}{(1.1)}  p(x_i)=\sumzjn a_j'\delta_{ij}=y_i\;\;\forall i=0,1,\dots,n
	\= \sist{a_0'=y_0\\
	a_1'=y_1\\
	\vdots\\
	a_n'=y_n
	}\\
	&p(x) \ubrace{=}{(1)} \sumzjn a_j'\l_j(x)=\sumzjn y_j\l_j(x)
	}
\end{proof}
\begin{prop}
	\def\l{{\lambda}}
	Nel contesto del thm \see{formalagrange} si ha
	\eal{&\sumzjn \l_j(x)(x_j-x)^k = \sist{1&k=0\\
	0&k>0}\;\;\forall x\in \R
	}
\end{prop}
\begin{proof}
	\def\l{{\lambda}}
Sia $f_k(x)$ il polinomio della tesi.
\eal{&f_0(x)= \sumzjn \l_j(x)
}
quindi $f_0(x)$ interpola i punti $(x_j,1)\;\;j=0,\dots,n$, quindi per
l'unicita' dell'interpolazione (\vedi{esisteunicasolinterpolpolinom}), si ha $f_0\equiv 1$.\\
Se $k>0$, si ha
\eal{& \l_j(x_i)(x_j-x_i)^k = \delta_{ij}(x_j-x_i)^k 
=\sist{0(x_j-x_i)^k & i \neq j\\
1\.0&i=j} =0 \> f_k(x_i)=0\;\;\forall i=0,\dots,n}
quindi $f_k(x)$ interpola i punti $(x_i,0)$. Allora, per l'unicita'
dell'interpolazione $f_k\equiv 0$.
\end{proof}

\begin{defn}
Sia $f\in \sczn{0}{[a,b]}$,\;\;$x_i\in [a,b]\;\;\forall i=0,1,\dots,n$
definiamo la \iemph{differenza divisa}:
\eal{&f[x_0]=f(x_0)\;\;\T{ ovvero la funzione $f$ calcolata in $x_0$}\\
&f[x_0,\dots,x_j]=\frac{f[x_1,\dots,x_j]-f[x_{0},\dots,x_{j-1}]}{x_j-x_0},\;\;\T{
per $j >0$}
}
\end{defn}
\begin{prop}\label{differenzedivisealgo}
	Il seguente e' un algoritmo che calcola $f[x_0,\dots,x_n]$ in
	$\frac{n(n+1)}{2}$ flops:
\eal{&a_i := f(x_i)\;\;\forall i=0,\dots,n\\
&\forall k=n-1,\dots,1,0\\
&\qq \forall i=0,\dots,k\\
&\qq \qq a_i := \frac{a_{i+1}-a_i}{x_{i+n-k}-x_i}\\
&\T{Il risultato e' in }a_0
}
si puo' visualizzare l'algoritmo cosi':
	\eal{&
\begin{matrix}
f[x_0]=f(x_0)   &            &               & \\
        &       & f[x_0,x_1] &               & \\
f[x_1]=f(x_1) & &            & f[x_0,x_1,x_2]& \\
        &       & f[x_1,x_2] &               & f[x_0,x_1,x_2,x_3]\\
f[x_2]=f(x_2) & &           & f[x_1,x_2,x_3] & \\
        &       & f[x_2,x_3] &               & \\
f[x_3]=f(x_3)  &           &               & \\
\end{matrix}
	}
\end{prop}

\begin{thm}\label{formadinewton}
Sia $f\in \sczn{0}{[a,b]}$,\;\;$x_i\in [a,b]\;\;\forall i=0,1,\dots,n$. Il
polinomio di Newton che interpola i punti $(x_i,f(x_i))$ e'
\eal{
&p_{n}(x)=\sum_{i=0}^{n}f[x_0,\dots,x_i]w_i(x)\\
&p_n(x_i)=f(x_i)\;\;\forall i=0,1,\dots,n
&\T{dove }\\
&\qq w_0(x)=1\\
&\qq w_j(x)=\prod_{i=0}^{j-1}(x-x_i)\;\;\forall j>0
}
$p_n(x)$ ha il vantaggio di poter essere facilmente aggiornato  per l'aggiunta
di nuovi punti. Infatti, dato $x_{n+1}$, basta calcolare
\eal{&p_{n+1}(x)=p_n(x)+f[x_0,\dots,x_{n+1}]w_{n+1}(x)}
Inoltre, vale la seguente proposizione:
\eal{
&f(x)=p_n(x)+R_n(x)\;\;\forall x\in [a,b]\\
&\T{dove }\\
&\qq
R_n(x)=f[x_0,\dots,x_n,x]w_{n+1}(x)\NN
\qq w_{n+1}(x)=\prod_{i=0}^{n}x-x_i
}
Infine, per calcolare $p_n(x)$ in $x$, si puo' usare il seguente algoritmo che
si basa sulla prop \see{calcolopolinomio}:
\eal{&t:=f[x_0,\dots,x_n]\\
&\forall i=1,\dots,n\\
&\qq t:=f[x_0,\dots,x_{n-i}]+t\cdot (x-x_{n-i})
}
Dove $f[x_0,\dots,x_{n-i}]$ si puo' calcolare con la prop
\see{differenzedivisealgo} (nota\footnote{in realta', non serve calcolare a
ogni passo  $f[x_0,\dots,x_{n-i}]$ usando \see{differenzedivisealgo}, perche'
alcuni calcoli vengono ripetuti inutilmente. Si puo' quindi pensare a
un algoritmo piu' ottimizzato.})
\end{thm}
\begin{proof}
	Poniamo $p_0(x)=f(x_0),\;p_{-1}(x)=0$
\step{p1}{Dim. che 
\eal{&\exists A_1,\dots,A_n\in \R:\;\;
p_k(x)=p_{k-1}(x)+A_kw_k(x)=\sum_{i=0}^{k}A_iw_i(x)\;\;\forall k=0,\dots,n
}
dove $p_k(x)\T{ e' il polinomio interpolatore di } (x_i,f(x_i))\;\;\forall
i=0,\dots,k$.
}
	\begin{prova}
Per Hp abbiamo:
\eal{&p_n(x_i)=f(x_i)\;\;\forall i=0,1,\dots,n}
Usando un polinomio incognita $g(x)$ di grado $\le  n+1$:
\eal{&p_{n+1}(x)=p_{n}(x)+g(x)\\
&p_{n+1}(x_i)=f(x_i)=p_n(x_i)  \;\forall i=0,\dots,n\>  g(x_i)=0 \;\;\forall
i=0,\dots,n\;\;(1)\\
&\sist{\deg p_{n+1}(x) \le n+1\\
\deg p_n(x)\le n}
\> \deg g(x) \le n+1\;\;(2)\\
&(1),(2)  \ubrace{\>}{\T{Ruffini}} g(x)=A_{n+1}\prod_{i=0}^{n}(x-x_i)
= A_{n+1}w_{n+1}(x)\\
&p_{n+1}(x)=p_{n}(x)+A_{n+1}w_{n+1}(x)\;\;(3)
}
In particolare abbiamo:
\eal{&p_0(x)=f(x_0)=\sum_{i=0}^{0}A_iw_i(x)\\
&p_1(x)=f(x_0)+A_1(x-x_0)=\sum_{i=0}^{1}A_iw_i(x)\\
&p_2(x)=f(x_0)+A_1(x-x_0) + A_2(x-x_0)(x-x_1)=\sum_{i=0}^{2}A_iw_i(x)\\
&\dots\\
&p_{n}(x)=\sum_{i=0}^{n}A_iw_i(x)
}
\end{prova}
Adesso resta da determinare gli $A_i$.
\step{pp2}{Dim. che vale la seguente implicazione:
\eal{&p_n(x)\T{ e' il polinomio interpolatore di } (x_i,f(x_i))\;\;\forall
i=0,\dots,n \> 
p_n(x)=\sum_{i=0}^{n}f[x_0,\dots,x_i]w_i(x)}
}
\begin{prova}
Procediamo per induzione su $n$.
\step{p21}{$n=0$}
\begin{prova}
	\eal{&p_0(x)=f(x_0)=f[x_0]}
\end{prova}
\step{}{$n=1$}
\begin{prova}
	\eal{&p_1(x) \ubrace{=}{\sref{p1}} p_0(x)+A_1(x-x_0)
	\ubrace{=}{\sref{p21}} 
	f[x_0] + A_1(x-x_0)
	}
Imponendo che $p_1(x_1)=f(x_1)$, abbiamo
\eal{&A_1=\frac{f(x_1)-f(x_0)}{x_1-x_0}=F[x_0,x_1]}
\end{prova}
\step{}{$n-1\> n$}
\begin{prova}
	Sia $h_{n-1}(x)$ il polinomio d'interpolazione relativo ai punti
	$x_1,\dots, x_n$, e $g_{n-1}(x)$ quello relativo ai punti
	$x_0,\dots,x_{n-1}$, ovvero
	\eal{
	&h_{n-1}(x_i) = f(x_i)\;\;\forall i= 1,\dots,n\;\;(4)\\
	&g_{n-1}(x_i) = f(x_i)\;\;\forall i= 0,\dots,n-1\;\;(4.1)
	}
	Si ha
	\eal{
	&p_n(x)= \frac{x-x_0}{x_n-x_0}h_{n-1}(x) +\frac{x_n-x}{x_n-x_0}g_{n-1}(x)\;\;(5)
	}
	infatti, 
	\eal{
	&x=x_0\>
	\frac{x_0-x_0}{x_n-x_0}h_{n-1}(x_0)
        +\frac{x_n-x_0}{x_n-x_0}g_{n-1}(x_0)=
	g_{n-1}(x_0)  \ubrace{=}{(4.1)} f(x_0)=p_{n}(x_0)\\
	&x=x_n \> 
	\frac{x_n-x_0}{x_n-x_0}h_{n-1}(x_n) +\frac{x_n-x_n}{x_n-x_0}g_{n-1}(x_n)
	= h_{n-1}(x_n)  \ubrace{=}{(4)} f(x_n)=p_n(x_n)\\
	&x=x_i,\;0<i<n \> 
	\frac{x_i-x_0}{x_n-x_0}h_{n-1}(x_i)
	+\frac{x_n-x_i}{x_n-x_0}g_{n-1}(x_i)=\\
	&
	\ubrace{=}{h_{n-1}(x_i)=f(x_i)=g_{n-1}(x_i)} 
	\pton{ \frac{x_i-x_0}{x_n-x_0}+\frac{x_n-x_i}{x_n-x_0}}
	f(x_i)=f(x_i)=p_n(x_i)
	}
	e quindi per l'unicita' di $p_n(x)$
	(\vedi{esisteunicasolinterpolpolinom}) si ha l'uguaglianza polinomiale
	nella $(5)$.\\
	Applicando l'ipotesi induttiva su $h_{n-1}$ e $g_{n-1}$
	abbiamo\footnote{se volessimo applicare l'Hp induttiva formalmente, ad esempio
	su $h_{n-1}$, basterebbe porre $y_0=x_1,y_1=x_2,\dots,y_{n-1}=x_n$}
	\eal{
	&h_{n-1}(x)=f[x_1]+f[x_1,x_2](x-x_1)
	+f[x_1,x_2,x_3](x-x_1)(x-x_2)+\dots+\\
	&\qq +f[x_1,x_2,\dots,x_{n}](x-x_1)(x-x_2)\dots (x-x_{n-1})\\
	&g_{n-1}(x)=f[x_0]+f[x_0,x_1](x-x_0)
	+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\dots+\\
	&\qq +f[x_0,x_1,\dots,x_{n-1}](x-x_0)(x-x_1)\dots (x-x_{n-2})
	}
	Indicando con $M(h_{n-1})$ il coefficiente dell'indeterminata grado massimo di
	$h_{n-1}$, abbiamo
	\eal{
	&M(h_{n-1})=f[x_1,x_2,\dots,x_{n}]\\
	&M(g_{n-1})=f[x_0,x_1,\dots,x_{n-1}]\\
	&M(p_{n}) \ubrace{=}{(5)} 
	\frac{M(h_{n-1})-M(g_{n-1})}{x_n-x_0}
	=\frac{f[x_1,x_2,\dots,x_{n}]-f[x_0,x_1,\dots,x_{n-1}]}{x_n-x_0}
	\ubrace{=}{\T{per def.}} f[x_0,\dots,x_n]\;\;(5.1)
	}
D'altra parte,
	\eal{&\sist{p_{n}(x) \ubrace{=}{(3)} p_{n-1}(x) +A_nw_n(x)\\
	\deg p_{n-1}(x) \le n-1\\
	\deg A_nw_n(x) \le  n\\
	w_n(x)\T{ e' monico}}
	\> M(p_{n})=M(A_nw_n(x))=A_n  \ubrace{=}{(5.1)} f[x_0,\dots,x_n]\\
	&p_n(x)= p_{n-1}(x) +  f[x_0,\dots,x_n]w_n(x)=\\
	&\qq 
	\ubrace{=}{\T{Hp induttiva su }p_{n-1}} 
	\sum_{i=0}^{n-1}f[x_0,\dots,x_i]w_i(x)  + f[x_0,\dots,x_n]w_n(x)=
	\sum_{i=0}^{n}f[x_0,\dots,x_i]w_i(x)
}
\end{prova}
\end{prova}
\step{}{Dim. che $f(x)=p_n(x)+R_n(x)\;\;\forall x\in [a,b]$}
\begin{prova}
	Fissiamo $x\in [a,b]$. Se consideriamo $(x_{n+1},f(x_{n+1}))\equiv
	(x,f(x))$ come un nuovo punto di
interpolazione, abbiamo
\eal{&f(x)=p_{n+1}(x) \ubrace{=}{\sref{pp2}} p_n(x)+f[x_1,\dots,x]w_{n+1}(x)
= p_n(x)+R_n(x)
}
\end{prova}
\end{proof}
\begin{prop}
	Nel contesto di \see{formadinewton}, si ha
	\eal{&\exists f^{(n+1)}(x) \T{ in } [a,b] \> 
	\exists \xi\in
	[a,b]:\;\;R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{n+1}(x)
	}
	dove $f^{(n+1)}(x)$ e' la derivata $n+1$-esima di $f$.
\end{prop}

\def\f{{\varphi}}
\def\a{{\alpha}}
\begin{prop}\label{polinomioChebyshev}
	Sia 
	\eal{&t_n(x)=\cos n \f(x):[-1,1]\longrightarrow \R\\
	&\f(x)=\arcos x:[-1,1]\longrightarrow [0,\pi]}
	$t_n(x)$ si puo' esprimere come un polinomio, chiamato \emph{polinomio
	di Chebyshev}:
	\eal{
	&t_0(x)=1\\
	&t_1(x)=x\\
	&t_n(x)=2t_{n-1}(x)x -t_{n-2}(x)\;\;\forall n>1
	}
	Valgono le seguenti proprieta':
	\eal{&\deg t_n(x) =n\;\;\forall n\ge 0\\
	&c_n=2^{n-1}\;\;\;\T{ coeff. di grado massimo di }t_n(x)\;\;\;\forall
	n\ge 1\\
	&\a_k=\cos\pton{\frac{\pi}{2n}+k\frac{\pi}{n}}\;\;k=0,\dots,n-1\;\;\;\;\T{ sono tutte
	le radici di }t_n(x)\\
	&M_k=\cos\pton{k\frac{2\pi}{n}}\;\;k=0,\dots,n\;\;\;\;\T{ sono tutti i punti di massimo}\\
	&m_k=\cos\pton{k\frac{2\pi}{n}+\frac{\pi}{n}}\;\;k=0,\dots,n\;\;\;\;\T{ sono tutti i
	punti di minimo}
	}
\end{prop}
\begin{proof}
	\eal{&
	t_{n+1}(x)=\cos((n+1)\f(x))=\cos(n\f(x)+\f(x))= \cos(n\f(x))\cos(\f(x)) -\sin(n\f(x))\sin(\f(x))\\
	&t_{n-1}(x)=\cos((n-1)\f(x))=\cos(n\f(x)-\f(x))=
	\cos(n\f(x))\cos(\f(x)) +\sin(n\f(x))\sin(\f(x))
	}
	Sommando membro a membro:
	\eal{&  t_{n+1}(x)+t_{n-1}(x) = 2\cos(n\f(x))\cos(\f(x)) =
	2t_n(x)x \=  t_{n+1}(x) = 2t_n(x)x -t_{n-1}(x)\\
	&t_{n}(x) = 2t_{n-1}(x)x -t_{n-2}(x)
	}
	\step{}{$\deg t_n(x)=n$}
	\begin{prova}
	Per induzione forte su $n$:
I casi $n=0,1$ sono veri.\\
\eal{&\deg t_n(x)= \deg \pqua{2t_{n-1}(x)x -t_{n-2}(x)}\\
&\deg t_{n-1}(x)x = \deg t_{n-1}(x) + 1  \ubrace{=}{\T{Hp induttiva}}
(n-1)+1=n\\
&\deg t_{n-2}(x)  \ubrace{=}{\T{Hp induttiva}} n-2\\
&\qq \> \deg t_n(x)= n
}
	\end{prova}
	\step{}{$c_n=2^{n-1}, \;n\ge 1$}
	\begin{prova}
		\eal{&t_1(x)=x\> c_1=1=2^{1-1}\\
		&\sist{t_{n}(x) = 2t_{n-1}(x)x -t_{n-2}(x) \\
		\deg 2t_{n-1}(x)x =n\\
		\deg t_{n-2} =n-2\\
		} \> c(t_n)=c(2t_{n-1}(x)x)=2c(t_{n-1}(x)x)=2c(t_{n-1})
		\ubrace{=}{\T{Hp induttiva}} 22^{n-2}=2^{n-1}}
		dove con $c(t_n)$ abbiamo indicato il termine di grado massimo
		di $t_n(x)$.
	\end{prova}
Infine, per ricercare le radici, i massimi e i minimi, basta cercare i punti
in cui la funzione $\cos n\f$ assume rispettivamente i valori $0,1,-1$,
e ricavarsi la $x$ sapendo che $x=\cos(\f)$.
\end{proof}
\begin{prop}
	Nel contesto della prop \see{polinomioChebyshev} si ha
	\eal{&\frac{1}{2^{n-1}} = \norm{\frac{1}{2^{n-1}}t_n(x)}_{[-1,1]}
	=\min\pgra{\norm{p}_{[-1,1]}\;|\;p\in \R[x]_n,\;\T{ $p$ monico
	}},\;\;\T{ con $n\ge 1$}}
	Nota: $\frac{1}{2^{n-1}}t_n(x)$ e' un polinomio monico.
\end{prop}
\begin{exemp}Fenomeno di Runge.\\
	Consideriamo la funzione
	\eal{&f(x)=\frac{1}{1+25x^2}:[-1,1]\longrightarrow \mathbb{R}}
	Se la interpoliamo in $n+1$ punti distribuiti uniformemente in
	$[-1,1]$, otteniamo una pessima approssimazione di $f(x)$, ovvero
	esistono alcuni punti $x\in [-1,1]$ dove $|f(x)-p_n(x)|$ e' molto
	alto. Al crescere di $n$ la situazione peggiora: si dimostra che per
	$n\to \8$ esistono degli $x\in [-1,1]$ t.c.  $|f(x)-p_n(x)|\to \8$.
	Vedi figura:
		\begin{center}
			\includegraphics[scale=0.5]{fig/runge}
		\end{center}
	$f(x)$ e' la linea in rosso.\\

	Se invece scegliamo le radici di Chebyshev come punti per
	l'interpolazione, abbiamo:
	\begin{center}
		\includegraphics[scale=0.5]{fig/runge2}
	\end{center}
	
	La miglioria e' dovuta al fatto che le radici di Chebyshev sono piu'
	distribuite verso gli estremi dell'intervallo $[-1,1]$.

	I grafici sono stati prodotti con il seguente script octave:
	\verbatiminput{fig/runge.m}
\end{exemp}

\begin{prop}
	\label{Lnapplineare}
Siano fissati $n+1$ punti $x_0,x_1,\dots,x_n \in [a,b]$.
Sia definita la seguente funzione:
\eal{&
L_n:\sczn{0}{[a,b]} \longrightarrow  \R[x]_n\\
&\T{$L_n(f)$ e' il polinomio che interpola $f$ nei punti $(x_i,f(x_i))\;\;\forall
i=0,\dots,n$ }
}
che e' ben definita per la prop \see{esisteunicasolinterpolpolinom}.\\
Si ha:
\eal{&
\T{	$L_n$ e' una applicazione lineare dello spazio vettoriale
$\sczn{0}{[a,b]}$ }}
\end{prop}
\begin{proof}
	\begin{prova}
		\def\a{{\alpha}}
		\def\b{{\beta}}
\eal{&L_n(\a f +\b g)(x_i) = (\a f +\b g)(x_i)=\a f(x_i) +\b g(x_i) = \a
L_n(f)(x_i)+\beta L_n(g)(x_i)\;\;\forall i=0,1,\dots,n\\
&\qq \> L_n(f)(x)+\beta L_n(g)(x)\T{ e' un polinomio interpolatore di }\a f
+\b g\T{ in } x_i\;\;\forall i=0,1,\dots,n
}
Quindi, per l'unicita' del polinomio interpolatore
(\vedi{esisteunicasolinterpolpolinom}) si ha
\eal{&L_n(\a f +\b g) = \a L_n(f)+\beta L_n(g)
}
	\end{prova}
\end{proof}

\section{Approssimazione polinomiale}
\begin{defn}
	L'approssimazione polinomiale consiste nel trovare un polinomio $p(x)$
	che approssimi una funzione $f(x)\in \sczn{0}{[a,b]}$.
\end{defn}
\begin{prop}\label{funzcontnormamax}
La funzione
\eal{&\norm{-}:\sczn{0}{[a,b]}\longrightarrow \R_+\\
&\norm{f} = \max_{x\in [a,b]}|f(x)|}
e' una norma nello spazio vettoriale $\sczn{0}{[a,b]}$.
\end{prop}
\begin{thm}\label{thmweierstrassI}
	di Weierstrass.\\
\eal{&(\R[x], \norm{-}) \T{ e' denso in } (\sczn{0}{[a,b]}, \norm{-})}
dove $\norm{-}$ e' la norma definita in \see{funzcontnormamax}, e $(\R[x]_n,
\norm{-}),\;\; (\sczn{0}{[a,b]}, \norm{-})$ sono spazi metrici indotti da
essa.
\end{thm}
\def\f{{\varphi}}
\begin{thm}\label{thmweierstrasII}
di Weierstrass II.\\
	Dato $n\ge 0$ e $f\in \sczn{0}{[a,b]}$, si ha
\eal{&\exists \f_n\in \R[x]_n:\;\;\forall \f\in \R[x]_n\;\;
\norm{f-\f_n} \le \norm{f-\f}}
Inoltre,
\eal{&\ulim{\f_n}{f}{[a,b]}
}
dove si e' intesa una convergenza uniforme.
\end{thm}
\begin{defn}\label{bernsteinpolinomio}
	Definiamo il polinomio di Bernstein:
	\eal{&B_{n,k}(x)= \binom{n}{k} x^k(1-x)^{n-k}
	}
\end{defn}
\begin{prop}
	Sia $B_{n,k}(x)$ il polinomio di Bernstein, si ha
	\eal{&1.\;\;\sum_{k=0}^n B_{n,k}(x) =1\\
	&2.\;\;\pgra{B_{n,0},B_{n,1},\dots,B_{n,n}\T{ e' una base di } K[x]_n }
	}
\end{prop}
\begin{proof}
	\step{}{Dim $1.$}
	\begin{prova}
	\eal{&1=x+1-x\\
	&1=(x+(1-x))^n=\sum_{k=0}^n\binom{n}{k} x^{k}(1-x)^{n-k}=\sum_{k=0}^n B_{n,k}(x) }
	\end{prova}
\end{proof}
\begin{thm}\label{approssimazionedibernstein}
	\label{bernsteinapprossimazione}
	Data una funzione $f(x)\in \sczn{0}{[0,1]}$, e posto 
	\eal{&B_n(f)(x)=\sumzkn f\pton{\frac{k}{n}} B_{n,k}(x) }
	si ha
	\eal{&\ulim{B_n(f)}{f}{[0,1]}}
\end{thm}
\begin{thm} di Faber.\\
	Sia 
	$V_k=\{x_1,\dots,x_k\}$, con $x_i\in [a,b]\;\;\forall i,\;\;x_i \neq
	x_j\;\;\forall i \neq j$. 
	Sia 
	$f(x)\in \sczn{0}{[a,b]}$, 
	$f_k(x)$ il polinomio interpolatore dei
	punti $(x_i,f(x_i))\;\;\forall i=1,\dots,k$. 
	Il teorema di Faber afferma che
	\eal{&\forall \pgra{V_k}_{k\in \mathbb{N}}\;\;
	\exists f(x)\in \sczn{0}{[a,b]}\T{ tale che }
	\lim_{k\to \8} f_k(x) \neq f(x)
	}
	In altre parole non e' sempre possibile usare con efficacia
un unico schema d'interpolazione per approssimare una qualunque funzione.
\end{thm}
\def\L{{\Lambda}}
\def\l{{\lambda}}

\begin{prop}
Data $f(x)\in \sczn{0}{[a,b]}$ sia $L_n(f)\in \R[x]_n$ il polinomio che interpola $f$ in
$n+1$ punti $(x_i,f(x_i))$. Si ha:
\eal{&\norm{f-L_n(f)} \le E_n(f)(1+\L_n)\\
&\ulim{E_n(f)}{0}{[a,b]}\\
&\lim_{n\to \8} \L_n = \8
}
dove
\eal{
&\norm{-} \T{ e' la norma definita in \see{funzcontnormamax} }\\
&E_n(f)=\norm{f-\f_n}, \T{ con $\f_n$ polinomio dato dalla prop.
\see{thmweierstrasII}}\\
&\L_n=\max_{x\in [a,b]} \sum_{i=0}^n|\l_i(x)|\T{ e' il numero di Lebesgue}\\
&\qq \T{dove }\lambda_j(x) \T{ sono dati da \see{formalagrange} rispetto ai
punti } x_0,x_1,\dots,x_n
}
\end{prop}
\begin{proof}
\eal{&
\norm{f - L_n(f)} = 
\norm{f -\f_n+\f_n- L_n(f)} \le 
\norm{f -\f_n}+\norm{\f_n- L_n(f)}  \ubrace{=}{\see{Lnapplineare}} 
\norm{f -\f_n}+\norm{L_n(\f_n-f)}  =\\
&= E_n(f)+\norm{L_n(\f_n-f)}\;\;(1)\\
&\norm{L_n(\f_n-f)} = \max_{x\in [a,b]} |L_n(\f_n-f)(x)| 
\ubrace{=}{\see{formalagrange}} \max_{x\in [a,b]}\Big|\sum_{i=0}^n
(\f_n(x_i)-f(x_i))\l_i(x)\Big| \le \\
&\le \max_{x\in [a,b]}\sum_{i=0}^n \pass{(\f_n(x_i)-f(x_i)
)}\pass{\l_i(x)} 
\le  \max_{x\in [a,b]}\sum_{i=0}^n \norm{\f_n(x)-f(x)}\pass{\l_i(x)} =\\
&
=  \max_{x\in [a,b]} \norm{\f_n(x)-f(x)} \sum_{i=0}^n \pass{\l_i(x)} 
= \norm{\f_n(x)-f(x)} \max_{x\in [a,b]} \sum_{i=0}^n \pass{\l_i(x)}
 = E_n(f)\L_n\\
 &(1)  \> \norm{f - L_n(f)} \le  E_n(f)+E_n(f)\L_n =E_n(f)(1+\L_n) 
	}
	Infine, per il thm \see{thmweierstrasII}
\eal{&\ulim{\f_n}{f}{[a,b]}  \> \ulim{E_n(f)}{0}{[a,b]}
}
\end{proof}
\subsection{Spline}
\begin{defn}
	Sia data una funzione $f:[a,b]\longrightarrow \mathbb{R}$.\\
	L'insieme delle spline di ordine $k$ e' definito come:
	\eal{&S_k=\pgra{s\in \sczn{k-1}{[a,b]}\;|\;
	s_{|[x_{i-1},x_i]}\in \R[x]_k,\;x_{i-1},x_i\in \Delta_n\;\;\forall
	i=1,\dots,n\;\;\T{ con }\Delta_n\T{ partizione di }[a,b]\T{ di $n$
	intervallini}}
	}
	In pratica, $s\in S_k$ e' una funzione, con derivata $k-1$ continua,
	e in ogni intervallino $[x_{i-1},x-i]$ e' un polinomio di grado $\le
	k$.\\
	Sia $s\in S_k$, definiamo
	\begin{description}
		\item[Spline naturale] Se $s''(a)=s''(b)=0$
		\item[Spline periodica] Se 
			\eal{&f(a)=f(b)\\
			&s_{+}'(a)=s_{-}'(b)\\
			&s_{+}''(a)=s_{-}''(b)
		}
	\end{description}
	Di seguito esamineremo solo le spline naturali di $S_3$.
\end{defn}
\begin{thm}\label{thmspline}
	L'algoritmo che costruisce la spline naturale $s\in S_3$ e':
	\begin{enumerate}
		\item Si risolve il seguente sistema lineare $AM=B$,
			nell'incognita $M$, usando l'algoritmo Gauss naive
			\see{gaussnaive} (nota\footnote{in realta' la matrice
			$A$ e' tri-diagonale, e quindi esistono algoritmi
			adatti che risolvono il sistema in $O(5n)$}
			\eal{&A\in \R^{n-1\*n-1},\;\;M,B\in \R^{n-1\*1}\\
&A_{ij}=\sist{2\pton{h_{i+1}+h_{i}} & i=j\\ 
h_{i+1} & j=i+1\\
h_{i} & j=i-1\\
0 & \T{altrimenti}
}\\
&B_i=6\pton{
\frac{{i+1}-y_{i}}{h_{i+1}}+\frac{{y_{i-1}-y_{i}}}{h_{i}}
}\;\;\forall i=1,\dots,n-1\\
&AM=B_i
}
\item Si calcolano i seguenti valori:
\eal{
&h_i=x_i-x_{i-1}\;\;\forall i=1,\dots,n\\
&\sist{A_{i} =
\pton{M_{i-1}-M_{i}}\frac{h_i}{6}-\frac{-y_{i}+y_{i-1}}{h_{i}}\\
B_{i} = -\frac{1}{6}M_{i}h_{i}^2+y_{i}}
}
\item
La funzione $s$ risulta essere 
	\eal{&
	s(x)=\sist{
	s_1(x)&x\in [x_0,x_1]\\
	s_2(x)&x\in [x_1,x_2]\\
	\dots\\
	s_n(x)&x\in [x_{n-1},x_n]
	}\\
&s_i(x)= 
M_{i}\frac{(x-x_{i-1})^3}{6h_i} +
M_{i-1}\frac{(x_i-x)^3}{6h_i}+A_i(x-x_i)+B_i
	}
	\end{enumerate}
\end{thm}
\begin{proof}
	Sia $s\in S_3$, fissiamo un $\Delta_n$ e poniamo
	\eal{&M_k=s''(x_k)\;\;\forall k=0,\dots,n\\
	&s_i=s_{|[x_{i-1},x_i]}\;\;\forall i=1,\dots,n\\
	&h_i=x_i-x_{i-1}\;\;\forall i=1,\dots,n
	}
	Esaminiamo $s_i$
	\eal{&s_i\in \R[x]_3 \> s_i=a_0+a_1x+a_2x^2+a_3x^3\>
	s_i''=2a_2+6a_3x\\
	&\sist{s_i''(x_i)=M_i\\
	s_i''(x_{i-1})=M_{i-1}\\
	\deg s_i''=1}  \ubrace{\>}{\T{ retta passante per due punti}} 
	s_i''(x)=
	M_{i}\frac{x-x_{i-1}}{x_{i}-x_{i-1}} +
	M_{i-1}\frac{x_i-x}{x_{i}-x_{i-1}}=
	M_{i}\frac{x-x_{i-1}}{h_i} +
	M_{i-1}\frac{x_i-x}{h_i}
	}
	La funzione $s''$ risulta essere 
	\eal{&
	s''(x)=\sist{
	s_1''(x)&x\in [x_0,x_1]\\
	s_2''(x)&x\in [x_1,x_2]\\
	\dots\\
	s_n''(x)&x\in [x_{n-1},x_n]
	}
	}
	ed e' gia' continua, infatti, se esaminiamo il punto di raccordo $x_i$
	\eal{&
	\lim_{x\to x_i^{-}} s''(x) = \lim_{x\to x_{i}^{-}}s_{i}''(x)
	\ubrace{=}{s_{i}''(x) \T{ e' continua } }  s_{i}''(x_i)=M_i\\
	&
	\lim_{x\to x_i^+} s''(x) = \lim_{x\to x_{i+1}^-}s_{i+1}''(x)
	=s_{i+1}''(x_i)=M_{i}\\
	&\lim_{x\to x_i^-} s''(x) = \lim_{x\to x_i^+} s''(x)
}
	Integrando $s_i''(x)$ ricaviamo $s_i'(x)$ e $s_i(x)$ (nota\footnote{
	stiamo sfruttando la seguente proprieta':\eal{&
	\int (x-a)^k\;dx  \ubrace{=}{y=x-a} \int y^k\;dy =
	\frac{y^{k+1}}{k+1}= \frac{(x-a)^{k+1}}{k+1}\\
	&
	\int (a-x)^k\;dx  \ubrace{=}{y=a-x} \int -y^k\;dy =
	\frac{-y^{k+1}}{k+1}= \frac{-(a-x)^{k+1}}{k+1}}
	}):
\eal{&
s_i'(x)= M_{i}\frac{(x-x_{i-1})^2}{2h_i} - M_{i-1}\frac{(x_i-x)^2}{2h_i}+A_i\\
&s_i(x)= 
M_{i}\frac{(x-x_{i-1})^3}{6h_i} +
M_{i-1}\frac{(x_i-x)^3}{6h_i}+A_ix+B_i' =
M_{i}\frac{(x-x_{i-1})^3}{6h_i} +
M_{i-1}\frac{(x_i-x)^3}{6h_i}+A_i(x-x_i)+B_i 
}
Nota: 
Imponiamo il passaggio di $s_i$ per i punti $(x_i,y_i=f(x_i))$,
$(x_{i-1},y_{i-1})$:
\eal{&\sist{
s_i(x_{i-1})=y_{i-1}\\
s_i(x_i)=y_i
}\= 
\sist{A_{i} =
\pton{M_{i-1}-M_{i}}\frac{h_i}{6}-\frac{-y_{i}+y_{i-1}}{h_{i}}\\
B_{i} = -\frac{1}{6}M_{i}h_{i}^2+y_{i}}
}
Imponiamo la continuita' di $s'(x)$ nei punti di raccordo:
\eal{&\lim_{x\to x_i^-}s'(x)=\lim_{x\to x_{i}^+}s'(x)\=
s_i'(x_i) = s_{i+1}'(x_i) 
\=\\
&\=
2\pton{h_{i+1}+h_{i}}M_{i}+h_{i+1}M_{i+1}+h_{i}M_{i-1}
=
6\pton{
\frac{{i+1}-y_{i}}{h_{i+1}}+\frac{{y_{i-1}-y_{i}}}{h_{i}}
}\;\;(1)
}
Considerando che stiamo usando la condizione
delle spline naturali
\eal{&
s''(a)=s''(b)=0\= 
s''(x_0)=s''(x_n)=0\= M_0=M_n=0
}
al variare di $i=1,\dots,n-1$, nella $(1)$ otteniamo un sistema lineare nelle $n-1$
incognite $M_i$ e $n-1$ equazioni:
\eal{&A\in \R^{n-1\*n-1}\\
&A_{ij}=\sist{2\pton{h_{i+1}+h_{i}} & i=j\\ 
h_{i+1} & j=i+1\\
h_{i} & j=i-1\\
0 & \T{altrimenti}
}\\
&\ove B_i=6\pton{
\frac{{i+1}-y_{i}}{h_{i+1}}+\frac{{y_{i-1}-y_{i}}}{h_{i}}
}\;\;\forall i=1,\dots,n-1\\
&AM=\ove B_i
}
Poiche'
\eal{&2\pton{h_{i+1}+h_{i}} \ubrace{\ge}{h_i\ge 0} h_{i+1}+h_{i}
}
si ha che $A$ e' a predominanza diagonale stretta e quindi
(\vedi{condizionegaussnaive}) possiamo usare
l'algoritmo Gauss naive (\vedi{gaussnaive}) per risolvere $AM=b$.
\end{proof}
\begin{prop}
	Sia $s\in S_3$ la spline naturale di $f\in\sczn{4}{[a,b]}$, si ha
	\eal{&|f(x)-s(x)| \le
	\max_{\xi\in[x_0,x_n]}f^{(4)}(\xi)\frac{5}{384}(\max_{j}h_j)^4\;\;\forall
	x\in [x_0,x_n]\\
	&h_j=x_{j}-x_{j-1}\;\;\forall j=1,\dots,n
	}
Questo assicura la buona approssimazione delle spline al diminuire di
$\max_{j}h_j$ e quindi all'aumentare di $n$.
\end{prop}
\section{Metodo dei minimi quadrati}
\def\f{{\varphi}}
\def\F{{\phi}}
\def\a{{\mathbf{a}}}
\def\x{{\mathbf{x}}}
\def\X{{\mathbf{v}}}
\def\y{{\mathbf{y}}}
\def\b{{\mathbf{b}}}
\begin{prop}
	\label{minimiquadrati}
	\begin{enumerate}
		\item Siano $m,n\in \mathbb{N},\;\;m<n$
		\item 
Siano dati i punti $(x_i,y_i)\in \R^2,\;\;i=1,\dots,n$ e i rispettivi vettori
$\x=(x_1,\dots,x_n),\y=(y_1,\dots,y_n)$
\item le funzioni
$\f_j(x):I\(\R \longrightarrow \R\;\;j=1,\dots,m$, con $x_i\in I\;\;\forall
i=1,\dots,n$
%\item $\f_j$ derivabile in $x_i\;\;\forall i=1,\dots,n,\;j=1,\dots,m$
\item Sia $\a=(a_1,\dots,a_m)\in \R^m$. Poniamo
\eal{&\f(x,\a)=\sumjm a_j\f_{j}(x)
}
\item Sia 
	\eal{
     &\F\in  \R^{n\*m},\;\;\;
\F_{jk}=\f_k(x_j)\\
	&S\in \R^{m\*m},\;\;\;
S_{jk}=\sumin  {\F}_{ij}\F_{ik}
= \sumin \f_j(x_i)\f_k(x_i),\;\= S=\TR \F\F
\\
     &\b\in \R^m,\;\;\;
     b_{j}=\sumin (\TR\F)_{ji}y_i =\sumin \f_j(x_i)y_i,\;\= b=\TR \F y
     }
Con $\F^k$ denotiamo la colonna $k$-esima di $\F$.
	\end{enumerate}
Supponendo che $\det S\neq 0$
il sistema
\eal{& S\a=\b \= \TR \F\F \a=\TR \F y}
ammette una ed una sola soluzione nell'incognita $\a$. Questa soluzione
minimizza la seguente funzione:
\eal{&E(\X)=\norm{\eps(\X)}_2^2:\;\;\R^{m}\longrightarrow \R\\
&\T{Dove }\\
&\qq \eps(\X): \R^m\longrightarrow \R^n\\
&\qq \eps(\X)_i = y_i- \f(x_i,\X)
}
$E(\X)$ indica di quanto la funzione $\f(x_i,\X)$  stia sbagliando
nell'approssimare i punti $(x_i,y_i)$. Infatti, se $\eps(\X)=\vz$, si avrebbe
\eal{&y_i- \f(x_i,\X)=\eps(\X)_i =0\=  \f(x_i,\X)=y_i\;\;\forall i=1,\dots,n
}
e quindi $\f(x,\X)$ sarebbe la funzione interpolante dei punti $(x_i,y_i)$.
Poiche' $m<n$, in generale non esistera' un $\X$ tale che  $\eps(\X)=\vz$. La
soluzione $\a$ garantisce pero' che $E(\a)$ sia il minimo errore, ovvero
\eal{&E(\a)\le E(\X)\;\;\forall \X\in \R^{m}}
\end{prop}
\begin{proof}
	Sia $\X\in \R^{m}$.
\eal{
&\eps(\X)_i = y_i-\f(x_i,\X) = y_i-\sumjm v_j\f_j(x_i)  =
y_i-\sumjm v_j\F_{ij}=
y_i- \F_i\X
}
dove $\F_i$ e' la $i$-esima riga di $\F$ e $\X$ e' inteso come colonna.
Quindi
\eal{&\eps(\X)=\y-\F\X
}
Dobbiamo minimizzare $\norm{\eps(\X)}_2^2$. Osserviamo che
\eal{&\norm{\eps(\X)}_2^2 = \norm{\y-\F\X}_2^2 = d(\F\X,\y)^2 
}
quindi dobbiamo trovare $\X$ in modo tale che la distanza tra i due
vettori $\F\X,\y$ sia minima.\\
Poiche'
\eal{&\F\X=\sumim \F^iv_i\\
&\T{ con  $\F^i$ la colonna $i$-esima di $\F$}
}
possiamo intepretare $\F\X$ come una combinazione linare dei vettori $\F^i$,
ovvero
\eal{&\pi_n=\ubrace{\Ll{\F^1,\dots,\F^n}}{\T{spazio
generato}}=\pgra{\F\X\;|\;\X\in \R^m}\\
}
\def\h{{\mathbf{h}}}
Se $n=2$, $\pi_2$ diventa un piano e il problema si puo' cosi'
interpretare: trovare quel punto $\F\a$ nel piano $\pi_2$ la cui distanza da $\y$ (che e' un
punto dello spazio) sia minima. Intuitivamente, $\F\a$ sembra essere la
proiezione ortogonale di $\y$ su $\pi_2$. Dimostreremo, nel caso generale, che e' proprio cosi'.
\step{}{
Sia $\F\a$ la proiezione di $\y$ su $\pi_n$. Si ha
\eal{&
\norm{\y-\F\a}_2^2 \le \norm{\y-\F\X}_2^2 \;\;\forall \X\in \R^m
}
ovvero
\eal{&
\norm{\eps(\a)}_2^2 \le\norm{\eps(\X)}_2^2 
\;\;\forall \X\in \R^m
}
}
\begin{prova}
Infatti, 
\eal{
& \y-\F\a\T{ e' il vettore che congiunge } \F\a \T{ con } \y \;\;(*)\\
&\F\a\in \pi_n\T{ e' la proiezione di }\y  \ubrace{\=}{(*)} 
(\y-\F\a)\perp \pi_n  \= 
\eps(\a) \perp \pi_n \= 
\eps(\a)\perp \F\X\;\;\forall \X\in \R^m 
\= \\
&\qq \= \ubrace{\eps(\a)\. \F\X}{\T{prodotto scalare}} =0 \;\;\forall \X\in \R^m
\;\;(1)\\
&\y-\F\X=\y-\F\a+\F\a-\F\X=
\y -\F\a +\F(\a-\X)=\eps (\a) + \F(\a-\X)\;\;(*)\\
&\norm{\y-\F\X}_2^2 = 
(\y-\F\a)\.(\y-\F\a)  \ubrace{=}{(*)}  
(\eps (\a) + \F(\a-\X))\.
(\eps (\a) + \F(\a-\X)) = \\
&=
\eps(\a)\.\eps(\a) + 2\eps (\a)\. \F(\a-\X)
+ \F(\a-\X)\. \F(\a-\X) \ubrace{=}{(1)} \eps(\a)\.\eps(\a) +
\F(\a-\X)\. \F(\a-\X)= \norm{\eps(\a)}_2^2+\norm{\F(\a-\X)}_2^2\\
&\norm{\y-\F\X}_2^2 = \norm{\eps(\a)}_2^2+\norm{\F(\a-\X)}_2^2 
\= \norm{\eps(\a)}_2^2 = \norm{\y-\F\X}_2^2 - \norm{\F(\a-\X)}_2^2
\> \norm{\eps(\a)}_2^2 \le  \norm{\y-\F\X}_2^2 =\norm{\eps (\X)}_2^2
}
Quindi per l'arbitrarieta' di $\X$ si ha la tesi.
\end{prova}
\step{}{Determiniamo $\a$}
\begin{prova}
Per la $(1)$, $\eps (\a) \perp \pi_n$
\eal{&\eps (\a) \perp \pi_n  \ubrace{\=}{\GII{proportobase} }
\eps(\a) \perp \F^i\;\;\forall i=1,\dots,n
\=
 \F^i\.\eps(\a) =0\;\;\forall i=1,\dots,n\=
 \\
 &\=
 \TR \F \eps (\a)=\vz \= 
  \TR {\F}(\y-\F\a)=\vz\=
  \TR {\F}\F\a=\TR {\F}\y\;\;(2)\\
  & (\TR {\F}\F)_{jk} = 
  \sumin (\TR {\F})_{ji}\F_{ik} =
  \sumin  {\F}_{ij}\F_{ik} = S_{jk} \> \TR {\F}\F=S\\
  &(\TR {\F}\y)_j = \sumin (\TR\F)_{ji}y_i = \b_j \> \TR {\F}\y=\b\\
 &(2) \= S\a=\b\;\;(2.1)
}
Quindi  $\a$ e' soluzione del sistema $(2.1)$. Poiche' per Hp $\det S \neq 0$,
$(2.1)$ ammette un unica soluzione.\\
Nota: il sistema $(2)$ viene chiamato \emph{sistema normale}.
\end{prova}
\step{}{Dimostrazione alternativa}
\begin{prova}
	Se le $\f_i$ sono derivabili e se le $\F^i$ sono vettori linearmente
	indipendenti si puo' procedere utilizzando il metodo
	di ricerca dei minimi relativi di una funzione reale:
	\begin{enumerate}
		\item Si impone $\nabla E(\X)=\vz$. Con opportuni calcoli si
			ha
			\eal{&\nabla E(\X)=\vz \= S\a=\b
			}
			Poiche' $\det S \neq 0$ l'unico punto critico e' $\a$.
		\item Si verifica che l'Hessiana $H(\a)$ e' definita positiva,
			e quindi $\a$ e' un punto di minimo (l'unico).
	\end{enumerate}
\end{prova}
\end{proof}
%\begin{defn}
%	\eal{&}
%\end{defn}
\begin{prop}
	\def\w{{\omega}}
\def\W{{\Omega}}
	Supponiamo di essere nella situazione della prop \see{minimiquadrati}.
	Stavolta, per ogni punto $(x_i,y_i)$ abbiamo a disposizione un numero
	$\w_i> 0$ che rappresenta il peso del punto stesso. Vogliamo che la
	funzione $\f(x,\a)$ sia piu' precisa nei punti che hanno maggior peso.
	Per far questo, basta definire un nuovo $\eps (\X)_i$:
	\eal{&\eps_\w(\X)_i = \w_i(y_i- \f(x_i,\X))}
	Ovviamente le quantita' in gioco cambieranno:
	\eal{
     &\F\in  \R^{n\*m},\;\;\;
\F_{jk}=\f_k(x_j)\\
&\W=\oname{diag}(\w_1,\w_2,\dots,\w_n)\in \R^{n\*n}\\
	&S'\in \R^{m\*m},\;\;\;
S_{ij}'
  = \sumkn \F_{ki}\w_k^2\F_{kj} =
  \sumkn \f_i(x_k)\f_j(x_k)\w_k^2 \;\= S'=\TR \F \TR  \W \W \F\\
  &\b'\in \R^m,\;\;\;
b_j'= \sumkn \F_{kj}\w_k^2y_k =\sumkn \f_j(x_k)\w_k^2y_k\;\=\b'=\TR \F\TR \W \W y
	}
Supponendo che $\det S'\neq 0$
il sistema
\eal{& S'\a=\b' \= \TR \F \TR  \W \W \F \a = \TR \F\TR \W \W y}
ammette una ed una sola soluzione nell'incognita $\a$. Questa soluzione
minimizza la funzione:
\eal{&E_\w(\X)=\norm{\eps_\w(\X)}_2^2
}
	\end{prop}
\begin{proof}
\def\W{{\Omega}}
	\def\w{{\omega}}
Procedendo come nella dimostrazione della prop \see{minimiquadrati}:
	\eal{
&\eps_\w(\X)_i = \w_i(y_i- \F_i\X )\\
&\eps_\w(\X)=\W (\y-\F\X)\\
&\T{dove }\\
&\qq \W 
= \begin{bmatrix}
\w_1& 0 & \ldots  &0	\\
0 & \w_2 & \ldots  &0	\\
\hdots\\
0 & 0 & \ldots  &\w_n
\end{bmatrix}\\
&\norm{\eps_\w(\X)}_2^2 = \norm{\W (\y-\F\X)}_2^2 =
(\W (\y-\F\X))\.(\W (\y-\F\X))=
\TR (\y-\F\X)\TR \W \W (\y-\F\X)\\
&\qq \TR \W \W 
= \begin{bmatrix}
\w_1^2& 0 & \ldots  &0	\\
0 & \w_2^2 & \ldots  &0	\\
\hdots\\
0 & 0 & \ldots  &\w_n^2
\end{bmatrix}
}
\def\vec#1{{\mathbf{#1}}}
Poiche' $\w_i>0$, $\TR \W \W$ e' definita positiva; e' anche simmetrica.
Quindi usando $\TR \W \W$ possiamo definire il seguente prodotto scalare (vedi
\GII{Spazio vettoriale euclideo}) e la sua rispettiva norma:
\eal{&x*y = \TR{\vec x}\TR \W \W\vec y\\
&\norm{x}_{*}=\sqrt{x*x}
}
Cosi' abbiamo:
\eal{&
\norm{\eps_\w(\X)}_2^2 = \TR (\y-\F\X)\TR \W \W (\y-\F\X)=
(\y-\F\X) * (\y-\F\X) = \norm{\y-\F\X}_{*}^2 =d_{*}(\F\X,\y)^2\\
&\norm{\eps_\w(\X)}_2^2 = \norm{\y-\F\X}_{*}^2 = \norm{\eps(\X)}_{*}^2
}
Quindi, utilizzando il nuovo prodotto scalare, 
possiamo ripetere la dimostrazione della prop \see{minimiquadrati}. Ripetiamo
qui di seguito, in forma sintetica, tutti i passaggi.
\step{}{
Sia $\F\a$ proiezione di $\y$ su $\pi_n$. Si ha
\eal{&
\norm{\eps(\a)}_*^2 \le\norm{\eps(\X)}_*^2 
\;\;\forall \X\in \R^m
}
}
\begin{prova}
Infatti, 
\eal{
& \y-\F\a\T{ e' il vettore che congiunge } \F\a \T{ con } \y \;\;(*)\\
&\F\a\in \pi_n\T{ e' la proiezione di }\y  \ubrace{\=}{(*)} 
(\y-\F\a)\perp \pi_n  \= 
\eps(\a) \perp \pi_n \= 
\eps(\a)\perp \F\X\;\;\forall \X\in \R^m 
\= \\
&\qq \= {\eps(\a)*\F\X} =0 \;\;\forall \X\in \R^m
\;\;(1)\\
&\y-\F\X=\y-\F\a+\F\a-\F\X=
\y -\F\a +\F(\a-\X)=\eps (\a) + \F(\a-\X)\;\;(*)\\
&\norm{\y-\F\X}_*^2 
= \norm{\eps(\a)}_*^2+\norm{\F(\a-\X)}_*^2\\
& \norm{\eps(\a)}_*^2 = \norm{\y-\F\X}_*^2 - \norm{\F(\a-\X)}_*^2
\> \norm{\eps(\a)}_*^2 \le  \norm{\y-\F\X}_*^2 =\norm{\eps (\X)}_*^2
}
Quindi per l'arbitrarieta' di $\X$ si ha la tesi.
\end{prova}
\step{}{Determiniamo $\a$}
\begin{prova}
Per la $(1)$, $\eps (\a) \perp \pi_n$
\eal{&\eps (\a) \perp \pi_n
\=
\F^i*\eps(\a) =0\;\;\forall i=1,\dots,n \ubrace{\=}{\T{def. di }*} 
 \TR {(\F^i)}\TR \W \W\eps(\a) =0\;\;\forall i\=\\
 &\=
 \TR \F \TR \W \W\eps (\a)=\vz \= 
  \TR {\F}\TR \W \W(\y-\F\a)=\vz\=
  \TR {\F}\TR \W \W\F\a=\TR {\F}\TR \W \W\y\;\;(2)\\
 &\T{Sia } D=\TR \W\W\\
 & (\TR {\F}\TR \W \W\F)_{jk} = 
  (\TR {\F}D\F)_{jk} =\\
  &\qq (D\F)_{ij}=\sumkn D_{ik}\F_{kj} =D_{ii}\F_{ij} = \w_i^2\F_{ij}\\
  &= \sumkn (\TR \F)_{ik}(D\F)_{kj}
  = \sumkn \F_{ki}\w_k^2\F_{kj} =
  \sumkn \f_i(x_k)\f_j(x_k)\w_k^2 = S_{ij}'\\
  &
  (\TR {\F}\TR \W \W\y)_j =
  (\TR {\F}D\y)_j =
  \sumkn (\TR {\F}D)_{jk}y_k=\\
  &\qq (\TR {\F}D)_{ij} = \sumkn (\TR \F)_{ik}D_{kj}=\sumkn
  \F_{ki}D_{kj} = \F_{ji}D_{jj} =\F_{ji}\w_j^2\\
  &= \sumkn \F_{kj}\w_k^2y_k =\sumkn \f_j(x_k)\w_k^2y_k=b_j'\\
 &(2) \= S'\a=\b'\;\;(2.1)
}
Quindi  $\a$ e' soluzione del sistema $(2.1)$. Poiche' per Hp $\det S' \neq 0$,
$(2.1)$ ammette un unica soluzione.
\end{prova}
\end{proof}
\begin{prop}
Supponiamo stavolta di volere approssimare un intero grafico di funzione
$(x,f(x))\;\;\forall x\in I=[a,b]$. Si procede analogamente a quanto visto in
\see{minimiquadrati}:
\begin{enumerate}
\item Sia 
	\eal{
&S\in \R^{m\*m},\;\;\;
S_{jk}=\intd{a}{b}
\f_j(x)\f_k(x)\;dx
\\
&\b\in \R^m,\;\;\;
b_{j}=\intd{a}{b}\f_j(x)f(x)\;\;dx
     }
	\end{enumerate}
Supponendo che $\det S\neq 0$
il sistema
\eal{& S\a=\b}
ammette una ed una sola soluzione nell'incognita $\a$. Questa soluzione
minimizza la seguente funzione:
\eal{&E(\X)=\intd{a}{b}\eps(x,\X)^2\;dx:\;\;\R^{m}\longrightarrow \R\\
&\T{Dove }\\
&\qq \eps(x,\X): I\*\R^m\longrightarrow \R\\
&\qq \eps(x,\X) = f(x)- \f(x,\X)
}
\end{prop}
\section{Equazioni non lineari}
\def\a{{\alpha}}
\begin{prop}\label{metodobisezione}
	Metodo di bisezione.\\
	Sia $f\in \sczn{0}{[a,b]}$, con $f(a)f(b)<0$, e posto
	\eal{&a_0=a,\;b_0=b\\
	&c_k=\frac{a_k+b_k}{2}\\
	&
	(a_{k+1},b_{k+1})=\sist{(c_k,b_k)&f(c_k)f(a_k)>0\\
	(a_k,c_k)&f(c_k)f(a_k)<0\\
	\T{non definita}&f(c_k)f(a_k)=0
%	(a_k,b_k)&f(c_k)f(a_k)=0
%	\pton{ c_k- \frac{b-a}{2^{k+2}} ,c_k+ \frac{b-a}{2^{k+2}} }&f(c_k)f(a_k)=0 
}
}
	Si ha che 
	\eal{&\exists k:\;f(c_k)=0 \;\| \;\limn c_n = \a\in ]a,b[\\
	&f(\a)=0}
	Ovvero, o un qualche $c_k$ e' uno zero di $f(x)$, oppure $c_n$
	converge a uno zero di $f$ in $[a,b]$.\\
Nel secondo caso, si ha 
\eal{&|b_k-a_k| < 2\eps \> |c_{k+1}-\a| < \eps }
Dove $|c_{k+1}-\a| $ e' l'errore di approssimazione della radice $\a$ dato da
$c_{k+1}$.\\
L'algoritmo che trova $c_k$ o una approssimazione di $\a$, con errore $<\eps
$, e' quindi il seguente:
	\eal{
	&\While:\\
	&\qq c:=\frac{a+b}{2}\\
	&\qq \Se |b-a| < 2\eps  \| f(c)=0:\\
	&\qq \qq \textbf{break}\\
	&\qq \Se f(c)f(a)>0:\\
	&\qq \qq a:=c\\
	&\qq \Se f(c)f(a)<0:\\
	&\qq \qq b:=c\\
	&\a:=c
}
\end{prop}
\begin{proof}
Se $\exists k:\;f(c_k)=0 $ non abbiamo nulla da dimostrare. Supponiamo allora
che
\eal{&\forall k\;\;f(c_k) \neq 0 \qq(0)}
Poiche' $f(a)f(b)<0$ possiamo supporre $f(a) >0$, $f(b)<0$.  Abbiamo allora 
\step{p00}{$f(a_k)> 0\;\;\forall k$}
\begin{prova}
	Per induzione.\\
	Caso base:
	\eal{&f(a_0)=f(a)>0
	}
	Supponiamo $f(a_k)>0$. Abbiamo tre casi
	\begin{enumerate}
		\item Se $f(c_k)f(a_k)>0$, allora
	$a_{k+1}=c_k$.
	Quindi
	\eal{&f(c_k)f(a_k)>0  \ubrace{\>}{f(a_k)>0} f(c_k) >0\\
	&f(a_{k+1})=f_(c_k)>0
	}
\item Se $f(c_k)f(a_k)<0$, allora $a_{k+1}=a_k$ e quindi la tesi e' vera.
\item Il caso $	f(c_k)f(a_k)=0$ non si puo' verificare perche' per la $(0)$
	si ha $f(c_k) \neq 0$.
	\end{enumerate}
\end{prova}
\step{p01}{$f(b_k)< 0\;\;\forall k$}
\begin{prova}
	Si procede analogamente a $\sref{p00}$
\end{prova}

Come abbiamo visto, il caso non definito della successione $(a_k,b_k)$ non
puo' verificarsi, quindi $(a_k,b_k)$ diventa una successione ben definita:
\eal{&	(a_{k+1},b_{k+1})=\sist{(c_k,b_k)&f(c_k)f(a_k)>0\\
	(a_k,c_k)&f(c_k)f(a_k)<0\\
}
}
a cui possiamo applicare tutti i teoremi di analisi.
	\step{p1}{$a_k\le b_k\;\;\forall k$}
	\begin{prova}
		Caso base: $a_0\le b_0$\\
		Supponiamo $a_k\le b_k$.
		Possono verificarsi due casi:
		\begin{enumerate}
			\item 
		Se $(a_{k+1},b_{k+1})=(c_k,b_k)$, allora
		\eal{&a_{k+1}=c_k=\frac{a_k+b_k}{2}
		\le b_{k+1}=b_k\=
		a_k+b_k\le 2b_k \= a_k\le b_k\T{ vera per Hp induttiva}
		}
	\item
		Se $(a_{k+1},b_{k+1})=(a_k,c_k)$, allora
		\eal{&a_{k+1}=a_k
		\le b_{k+1}=c_k
		=\frac{a_k+b_k}{2}
		\=
		2a_k \le  a_k+b_k \=
		\= a_k\le b_k\T{ vera per Hp induttiva}
		}
		\end{enumerate}
	\end{prova}
	\step{p2}{$a_{k+1}\ge a_k$}
	\begin{prova}
		Se $a_{k+1}=a_k$ allora la tesi e' vera.\\
		Se $a_{k+1}=c_k$, si ha
		\eal{&a_{k+1}=c_k =\frac{a_k+b_k}{2} 
		\ge a_k \=
		a_k+b_k \ge 2a_k \= b_k \ge a_k\T{ vera per \sref{p1}}
		}
	\end{prova}
	\step{p3}{$b_{k+1}\le  b_k$}
	\begin{prova}
		Se $b_{k+1}=b_k$ allora la tesi e' vera.\\
		Se $b_{k+1}=c_k$, si ha
		\eal{&b_{k+1}=c_k =\frac{a_k+b_k}{2} 
		\le  b_k \=
		a_k+b_k \le  2b_k \= a_k \le b_k\T{ vera per \sref{p1}}
		}
	\end{prova}
	\step{p4}{$b_k-a_k=\frac{b-a}{2^k}$}
	\begin{prova}
		\eal{&b_0-a_0=b-a=\frac{b-a}{2^0}
		}
		Supponiamo la tesi vera per $k$.\\
	Possono verificarsi due casi:
		\begin{enumerate}
			\item 
		Se $(a_{k+1},b_{k+1})=(c_k,b_k)$, allora
	\eal{&b_{k+1}-a_{k+1}=b_k-c_k=b_k-\frac{a_k+b_k}{2}= 
	\frac{b_k-a_k}{2} \ubrace{=}{\T{Hp indutt.}} 
	\frac{\frac{b-a}{2^k}}{2}=
	\frac{b-a}{2^{k+1}}
		}
	\item
		Se $(a_{k+1},b_{k+1})=(a_k,c_k)$, allora si procede
		analogamente a prima.
		\end{enumerate}

	\end{prova}
	Abbiamo:
	\eal{&
a_0 \ubrace{\le }{\sref{p2}}
a_k \ubrace{\le  }{\sref{p1}} b_k \ubrace{\le }{\sref{p3}} b_0\;\;(1)\\
}
$a_k$ e' quindi una successione non decrescente, limitata superiormente,
quindi converge ad un $\a$, che per la $(1)$ e' in $[a,b]$.\\
\def\b{{\beta}}
Analogamente $b_k$ converge a $\b$. Abbiamo che $\a=\b$, infatti,
\eal{&
\sist{\limn b_n-a_n \ubrace{=}{\sref{p4}} \limn \frac{b-a}{2^n}
 =0\\
a_n\le b_n} \>  
\limn b_n =\limn a_n \= \a=\b\;\;(2)\\
&\limn c_n = \limn \frac{a_n+b_n}{2} = \a\;\;(2.1)
}

Infine, poiche' $f$ e' continua in $[a,b]$ e $\a\in [a,b]$, si ha
\eal{
&\lim f(a_n) =f(\lim a_n)= f(\a)\;\;(3.1)\\
&\lim f(b_n) =f(\lim b_n)= f(\a)\;\;(3.2)
}
Per il \sref{p00} e il \sref{p01} si ha
\eal{
&f(a_k)>0\;\;\forall k \> \lim f(a_n) \ge 0 \ubrace{\=}{(3.1)}  f(\a) \ge 0\\
&f(b_k)<0\;\;\forall k \> \lim f(b_n) \le 0 \ubrace{\=}{(3.1)}  f(\a) \le  0\\
&\qq \> f(\a)=0
}
che e' la tesi.
\step{}{Dimostriamo che 
\eal{&|b_k-a_k| < 2\eps \> |c_{k+1}-\a| < \eps }
}
\begin{prova}
\eal{
&a_k\T{ non decrescente }  \> \lim a_k=\sup a_k \= \a = \sup a_k \> \a \ge a_k\;\;\forall k\\
&b_k\T{ non crescente }  \> \lim b_k=\inf a_k \= \a = \inf a_k \> \a \le  b_k\;\;\forall k\\
&c_k\T{ e' il punto medio di }[a_k,b_k] \>  c_k\in ]a_k,b_k[\\
&\a, c_k\in ]a_k,b_k[ \> |c_k-\a| \le  
|b_k-a_k| \ubrace{<}{\T{per Hp}} 2\eps \;\;(+)\\
&|b_k-a_k|  \ubrace{=}{\sref{p4}} \frac{b-a}{2^{k}} \ubrace{<}{(+)} 2\eps  \=  
\frac{b-a}{2^{k+1}} <  \eps \;\;(*)\\
&|c_{k+1}-\a| \ubrace{\le}{(+)}  |b_{k+1}-a_{k+1}| \ubrace{=}{\sref{p4}} 
\frac{b-a}{2^{k+1}} \ubrace{< }{(*)} \eps 
}	
\end{prova}
\end{proof}

\begin{prop}\label{metodonewton}
	Metodo di Newton.\\
	Sia 
	\begin{enumerate}
		\item 
	$f\in \sczn{2}{[a,b]}$\\
\item $f(a)f(b)<0$
\item  $f'(x) \neq 0\;\;\forall x\in [a,b]$
\item $f''(x)> 0\;\;\forall x\in [a,b]$ oppure
	$f''(x) < 0 \;\;\forall x\in [a,b]$
	\end{enumerate}
	Definita la successione
	\eal{
	&x_0=\sist{a& f(a)f''(a) >0\\ 
	b&f(b)f''(b) >0
	}\\
	&x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}
	}
	che risulta essere ben definita ($x_n\in [a,b]\;\;\forall n$), si ha
	\eal{&
	\limn x_n =\a\in [a,b]
	}
dove $\a$ e' uno zero di $f$, ovvero $f(\a)=0$.\\
	Geometricamente la successione $x_n$ si puo' interpretare come segue:
	\begin{enumerate}
		\item si calcola la retta tangente in $x_k$
		\item $x_{k+1}$ e' il punto di intersezione di tale retta con
			l'asse $y=0$
	\end{enumerate}
\end{prop}
\begin{proof}
	Supponiamo di essere nel caso 
	$f''>0,\;\;f(b)f''(b)>0,\;x_0=b$.
	Analogamente si dimostrano gli altri casi.
	\step{p0}{$f(x_k)>0\;\;\forall k$}
	\begin{prova}
Poiche' $f''(x)>0\;\;\forall x\in [a,b]$, si ha che $f$ e' convessa in ogni punto
		(volge sempre la concavita' verso l'alto,
		vedi \AI{thmconcavita}). Quindi nel punto 
		$x_k$ abbiamo:
		\eal{
		&\exists \delta>0:\;\;f(x)>f(x_k)+f'(x_k)(x-x_k)\;\;\forall
		x\in ]x_k-\delta,x_k+\delta[\-\pgra{x_k}}
		Vale il realta' un risultato piu' forte, la funzione $f$ e'
		convessa e si ha:
		\eal{&f(x)>f(x_k)+f'(x_k)(x-x_k)\;\;\forall x \neq x_k\;\;(*)
		}
		Allora
		\eal{
		&x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)}
		\= f'(x_k)(x_{k+1} -x_k)+f(x_k)=0\\
		&f(x_{k+1})\ubrace{>}{(*)} f(x_k)+f'(x_k)(x_{k+1}-x_k)=0\\
		&f(x_{k+1})>0
		}
	\end{prova}
	\step{}{$f$ e' crescente e $f'>0$}
	\begin{prova}
		\eal{&f''>0,\;f(b)f''(b) >0\> f(b) >0  \ubrace{\>}{f(a)f(b)<0}
		f(a)< 0\\
		&f'>0 \| f'<0\T{ infatti, se per assurdo }\exists x,x':\;\;
		f'(x)f'(x') <0  \ubrace{\>}{f'\T{ continua}, \T{thm esistenza
		zeri}}  \exists \xi:\;f'(\xi)=0\T{ assurdo }\NN
		f'>0 \| f'<0 \> f\T{ monotona} \NN
		\sist{f(a)<0,\;f(b)>0\\
		f\T{ monotona}} \> f\T{ crescente} \> f'>0
		}
	\end{prova}
	\def\a{{\alpha}}
	\step{}{$\exists !\a\in[a,b]:\;f(\a)=0$, inoltre, $a<
	\a<x_{k+1}<x_k<x_0=b$}
	\begin{prova}
	Poiche' $f(a)f(b)<0$, per il thm degli zeri, $\exists \a\in
	[a,b]:\;f(\a)=0$. Se per assurdo $\exists \a' \neq \a:\;f(\a')=0$,
	allora
	\eal{&f(\a)=f(\a')=0,\;f\T{ continua} \ubrace{\>}{\T{thm di Rolle}}
	\exists \xi\in [\a,\a']:\;f'(\xi)=0\T{ assurdo}}
	Quindi $\a$ e' unico.
	\eal{&\sist{f(\a)=0,\;f(x_k)\ubrace{>}{\sref{p0}}0\\
	f\T{ crescente}}\> \a < x_k 
	}
Per i passi precedenti abbiamo $f(x_k),f'(x_k)>0$, e quindi
\eal{&\frac{f(x_k)}{f'(x_k)} >0 \> x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)}
<x_k\\
&x_{k+1}<x_k\>\pgra{x_k}\T{ e' decrescente }\\
&\a < x_k< x_0 = b\>\pgra{x_k}\T{ e' limitata}\\
&\qq \> \exists \limn x_n =l
}
Prendendo il limite in $x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}$, per la
continuita' di $f$, abbiamo
	\eal{&l=l-\frac{f(l)}{f'(l)}\= f(l)=0
	}
Per l'unicita' di $\a$, si ha $l=\a$.
	\end{prova}
\end{proof}
\begin{prop}\label{metodosecanti}
	Metodo delle secanti.\\
	Questo metodo e' analogo a quello di Newton, ma al posto di usare la
	retta tangente, si usa una retta secante (che sia abbastanza vicina
	alla tangente). La successione diventa:
	\eal{&
	x_{k+1}=x_k-f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}
	}
\end{prop}
\begin{prop}\label{metodomisto}
	Metodo misto.\\
	Il metodo di bisezione converge sempre ma e' molto lento.\\
	Il metodo di Newton non sempre converge, ma e' molto rapido.\\
	Si puo' pensare quindi di combinare i due metodi. Ad esempio, 
	\begin{enumerate}
		\item \label{ouasd}
	Si usa
	il metodo di bisezione di per restringere l'intervallo di ricerca
\item Si applica il metodo di Newton, usando un massimo $m$ di iterazioni.
\item Se il massimo $m$ e' stato raggiunto e lo zero non e' stato trovato, si
	ritorna al punto \ref{ouasd}
	\end{enumerate}
\end{prop}
\subsection{Ricerca di punti fissi}
\def\a{{\alpha}}
\def\f{{\phi}}
\begin{prop}\label{esistepuntofisso}
\eal{&	\sist{\f:[a,b]\longrightarrow [a,b]\\
	\f\in \sczn{0}{[a,b]} }  \> \exists \a\in [a,b]:\;\a=\f(\a)
}
\end{prop}
\begin{proof}
Sia $F(x)=x-\f(x)$.
Se $F(a)=0$, allora $\a=a$. Altrimenti
\eal{&\f(a)\in [a,b] \> \f(a) \ge a \= a-\f(a)\le 0  \ubrace{\=}{F(a) \neq 0}
a-\f(a)<0\=F(a)<0
}
Se $F(b)=0$ allora $\a=b$, altrimenti
\eal{&\f(b)\in [a,b] \> \f(b) \le b \= b-\f(b)\ge  0  \ubrace{\=}{F(b) \neq 0}
b-\f(b)>0\=F(b)>0
}
Allora
\eal{&
\sist{F(a)<0,\;F(b)>0\\
\f(x)\T{ continua } \> F(x)\T{ continua}
} \ubrace{\>}{\T{thm esistenza zeri}}\exists \a\in ]a,b[:\;F(\a)=0\=\f(\a)=\a
} 
\end{proof}
\begin{prop}\label{esistepuntofissounico}
Sia \begin{enumerate}
	\item $\f:[a,b]\longrightarrow [a,b]$
	\item $\f\in \sczn{0}{[a,b]}$
	\item Si verifica almeno una delle seguenti condizioni:
		\begin{enumerate}
			\item 
		$\f\T{ e' Lipschitziana di costante }0<L<1$, ovvero 
		\eal{&|\f(x)-\f(y)| \le  L|x-y|\;\;\forall x,y\in [a,b]
		}
	\item
	oppure $\f\in \sczn{1}{[a,b]}$ con 
	\eal{&|\f'(x)|\le L <1\;\;\forall x \in [a,b]}
		\end{enumerate}
	\item $x_0\in [a,b]$, $x_{k+1}=\f(x_k)$
\end{enumerate}
allora 
\eal{&
	\exists! \a\in [a,b]:\;\a=\f(\a)\\
	&\limn x_n = \a
}
\end{prop}
\begin{proof}
	Per la prop \see{esistepuntofisso}, sappiamo che $\a$ esiste.
	Supponiamo per assurdo che  esistano  $\a_1 \neq \a_2$ t.c. $\f(\a_i)=\a_i$,
	allora
	\case{Caso $(a)$: $\f$ Lipschitziana}
	\begin{prova}
		
	\eal{&|\a_1-\a_2| = |\f(\a_1)-\f(\a_2)| \le  L|\a_1-\a_2|
	\ubrace{<}{L<1,\;\;\a_1 \neq \a_2}
	|\a_1-\a_2|\\
	&|\a_1-\a_2|<|\a_1-\a_2|
	}
	Assurdo.\\
	\end{prova}
	\case{Caso $(b)$: $|\f'(x)|<1\;\;\forall x\in [a,b]$}
	\begin{prova}
Poiche' $\a_1 \neq \a_2$, a meno di riordinare gli indici, possiamo supporre
$\a_1<\a_2$. Applichiamo il teorema di Lagrange:
\eal{&\f(x)\in \sczn{1}{[a,b]}
\ubrace{\>}{\T{Lagrange}} 
		\exists d\in ]\a_1,\a_2[:\;\;
                \f(\a_2)-\f(\a_1) = \f'(d) (\a_2-\a_1)\=\\
		&\frac{\f(\a_2)-\f(\a_1)}{\a_2-\a_1}=\f'(d)\=
		\frac{\a_2-\a_1}{\a_2-\a_1}=\f'(d) \= 
		\f'(d)=1
}
assurdo contro ipotesi.
	\end{prova}
	\step{}{$|x_n-\a|\le L^n|x_0-\a|$
	}
	\begin{prova}
		Per induzione.\\
		Base:
		\eal{&|x_0-\a|\le L^0|x_0-\a|
		}
		Passo induttivo:
		\case{Caso $(a)$: $\f$ Lipschitziana}
		\begin{prova}
		\eal{&
	|x_{n+1}-\a|=|\f(x_n)-\f(\a)|\le L|x_n-\a|
	\ubrace{\le }{\T{Hp indutt.}} LL^n|x_0-\a|=L^{n+1}|x_0-\a|
		}
		\end{prova}
		\case{Caso $(b)$}
		\begin{prova}
	Se $x_n=\a$, allora
	\eal{&x_{n+1}=\f(x_n)=\f(\a)=\a\\
	&|x_{n+1}-\a|=0\le L^{n+1}|x_0-\a|
	}
		Supponiamo $\a<x_n$.
Applichiamo Lagrange a $\f(x)$ nell'intervallo $[\a,x_n]$, ottenendo:
\eal{&\exists d\in ]\a,x_n[:\;\f(x_n)-\f(\a) = \f'(d)(x_n-\a)\\
&|x_{n+1}-\a|=|\f(x_n)-\f(\a)|=|\f'(d)| |x_n-\a| \le 
L |x_n-\a| \ubrace{\le }{\T{Hp indutt.}} LL^n|x_0-\a|=L^{n+1}|x_0-\a|
}
		\end{prova}
	\end{prova}
Poiche' 
$0\le L<1$ si ha $L^n\to 0$, quindi prendendo il limite in 
\eal{& 0\le |x_n-\a|\le L^n|x_0-\a|
	}
abbiamo (per il thm del confronto) che:
\eal{&\limn |x_n-\a| =0 \= \limn x_n =\a
}
\end{proof}
\begin{prop}\label{puntofissochenonconverge}
Sia \begin{enumerate}
	\item $\f:[a,b]\longrightarrow \R$
	\item $\f\in \sczn{1}{[a,b]}$ con 
	\eal{&|\f'(x)| \ge L> 1\;\;\forall x \in [a,b]}
	\item $x_0 \in [a,b]$, $x_{k+1}=\f(x_k)$
	\item $\a\in [a,b],\;\f(\a)=\a$ 
	\item $x_0 \neq \a$
\end{enumerate}
allora, 
la successione $x_n$ \textbf{non} converge al punto fisso $\a$. Anzi, la
successione $x_n$ non e' nemmeno ben definita:
\eal{&\exists k:\;x_k\notin [a,b]
}
\end{prop}
\begin{proof}
	\step{}{$|x_n-\a| \ge  L^n|x_0-\a| >0$
	}
	\begin{prova}
		Per induzione.\\
		Base:
		\eal{&|x_0-\a| \ge  L^0|x_0-\a|  = |x_0-\a| \ubrace{>}{x_0
		\neq \a}0
		}
		Passo induttivo:
Per Hp induttiva $|x_n-\a| >0$ e quindi $x_n \neq \a$.
Supponiamo $\a<x_n$.
Applichiamo Lagrange a $\f(x)$ nell'intervallo $[\a,x_n]$, ottenendo:
\eal{&\exists d\in ]\a,x_n[:\;\f(x_n)-\f(\a) = \f'(d)(x_n-\a)\\
&|x_{n+1}-\a|=|\f(x_n)-\f(\a)|=|\f'(d)| |x_n-\a| \ubrace{\ge}
{|\f'(x)| \ge L}
L |x_n-\a| \ubrace{\ge }{\T{Hp indutt.}} LL^n|x_0-\a|=L^{n+1}|x_0-\a| >0
}
	\end{prova}
Quindi:
	\eal{& |x_n-\a| \ge  L^n|x_0-\a|\;\;\forall n
}
e poiche' $L>1$, prendendo il limite, si ha
\eal{&\limn |x_n-\a| = +\8 \> \limn x_n  \neq \a
}
Infine, se per assurdo $x_n\in [a,b]\;\;\forall n$, allora
\eal{&x_n,\a\in [a,b] \;\;\forall n\> |x_n-\a| \le |b-a|\;\;\forall n
\> \limn |x_n-\a| \le  |b-a|
}
assurdo contro $\limn |x_n-\a| = +\8 $
\end{proof}

\def\d{{\delta}}
\begin{prop}\label{puntofissocondf}
Sia \begin{enumerate}
	\item $\f:[a,b]\longrightarrow \R$
	\item $\f\in \sczn{1}{[a,b]}$
	\item $x_0\in [a,b]$, $x_{k+1}=\f(x_k)$
	\item $\a=\f(\a)$ 
\end{enumerate}
allora 
\eal{&|\f'(\a)| <1 \> \exists \d>0:\;\;(x_0\in I_\d\> \limn x_n=\a)\\
&\T{dove } I_\d=[\a-\d,\a+\d] \( [a,b]
}
\end{prop}
\begin{proof}
\eal{&|\f'(\a)| <1 \> \exists \eta:\;\;|\f'(\a)| < \eta < 1\\
&\sist{\T{$\f'$ e' continua }\\
|\f'(\a)| <\eta}  \ubrace{\>}{\T{permanenza del segno}}  \exists
\d>0:\;\;|\f'(x)|<\eta<1 \;\;\forall x\in I_\d\;\;(1)
}
Sia $x_0\in I_\d$. Se $\exists m:\;x_n=\a$, allora non abbiamo nulla da
dimostrare dato che $x_n$ diventa la successione costante $\pgra{\a}$.
Supponiamo quindi che
\eal{&\forall n:\;\;x_n \neq \a
}
\step{}{Dimostriamo che 
\eal{&x_n\in I_\d,\;\;|x_n-\a|\le  |x_0-\a|\;\;\forall n\\
&|x_{n}-\a|<\eta^n |x_0-\a|}
}
	\begin{prova}
Per induzione.\\
		Base:
	\eal{&|x_0-\a|\le \eta^0|x_0-\a|
		}
		Passo induttivo:
		\eal{&x_n\in I_\d\( [a,b]\T{ per Hp induttiva. Supponiamo $x_n \neq
		b$ e $\a<x_n$}\\
		&\f\in \sczn{1}{[a,b]} 
		\ubrace{\>}{x_n\in [a,b[,\;\a\in [a,b],\;\a \neq x_n} \f\in
		\sczn{1}{[\a,x_n]}
		\ubrace{\>}{\T{thm di Lagrange}} 
		\exists \xi_n\in ]\a,x_n[:\;\;
                \f(x_n)-\f(\a) = \f'(\xi_n) (x_n-\a)\;\;(*)\\
		&\xi_n\in ]\a,x_n[ \= \a< \xi_n < x_n \le  \a+\d\\
		&\qq \a-\d <\a <\xi_n < \a+\d \> \xi_n\in ]\a-\d,\a+\d[=I_\d\\
		&\qq  \ubrace{\>}{(1)} |\f'(\xi_n)|<\eta<1\;\;(**)\\
&	|x_{n+1}-\a|=|\f(x_n)-\f(\a)|
	\ubrace{=}{(*)} |\f'(\xi_n)| |x_n-\a| 
	\ubrace{<}{x_n \neq \a,\;\;(**)} \eta  |x_n-\a| \le \\
	&
	\ubrace{\le }{\T{Hp induttiva}} \eta \eta^n|x_0-\a|=\eta^{n+1}|x_0-\a|
	\ubrace{<}{\eta < 1} |x_0-\a|
	\ubrace{\le }{x_0\in I_\d}
	\d\\
	&|x_{n+1}-\a| \le \d \> x_{n+1}\in I_\d\\
	&|x_{n+1}-\a| <\eta^{n+1}|x_0-\a|
	}
	\end{prova}
Prendendo il limite in 
\eal{& 0\le |x_n-\a|\le \eta^n|x_0-\a|
	}
poiche' $0\le \eta<1$, $\eta^n\to 0$, quindi per il thm del confronto
\eal{&\limn |x_n-\a| =0 \= \limn x_n =\a
}
\end{proof}

\begin{prop}
	Supponiamo di volere risolvere l'equazione
	\eal{&f(x)=g(x)}
	Se $f$ ammette l'inversa, possiamo ricondurci alla ricerca di un punto
	fisso:
	\eal{&x=\inv f g(x)=\f_1(x)}
	Se $g$ ammette l'inversa, possiamo ricondurci a:
	\eal{&x=\inv g f(x)=\f_2(x)}
Scelta $\f_1$ o $\f_2$ possiamo cercare di applicare i thm fin'ora visti.\\
Supponendo che $f,g$ ammettano le inverse, possiamo decidere quale delle due
$\f_i$ preferire, infatti
\eal{
&|\f_1'(x)| < 1  \;\;\forall x\in [a,b] \=  |\f_2'(x)| >1\;\;\forall x\in
[a,b]\\
&|\f_1'(x)| > 1 \;\;\forall x\in [a,b] \=  |\f_2'(x)| <1\;\;\forall x\in [a,b]
}
Poiche' vogliamo sfruttare il thm \see{esistepuntofissounico}, sceglieremo
quindi la $\f_i$ t.c. $|\f_i'(x)|<1$\\
Infine, osserviamo che dal problema della ricerca di un punto fisso possiamo
passare al problema della ricerca di uno zero di funzione:
\eal{&x=h g(x) \T{ ricerca del punto fisso}\\
&\inv h(x)=g(x) \= \inv h(x)-g(x)=0\T{ ricerca di zero di funzione }
}
\end{prop}
\begin{proof}
Basta osservare che
\eal{&\f_1(x)=\inv {\f_2}(x)
}
e applicare il thm di derivazione della funzioni inverse (vedi
\AI{thm_deriv_inv}):
\eal{&\f_1'(x) = D\pqua{\inv {\f_2}(x)}
= \frac{1}{\f_2'(\inv \f_2(x))}\\
&|\f_1'(x)| = \frac{1}{|\f_2'(\inv \f_2(x))|}
}
\end{proof}
\subsection{Ordine di convergenza}
\begin{defn}
	Consideriamo una  successione  $x_n$ che converge ad $\a$, e sia
	$e_n=x_n-\a$. Per misurare quanto rapidamente la successione converge,
	poniamo
	\eal{&E_{n,p}=\frac{|e_{n+1}|}{|e_n|^p}}
	e  diamo le seguenti definizioni
	\eal{&x_n\T{ ha 
\iemph{ordine di convergenza} (O.C.) } 1
	\definizione{ \=} 
	\limn E_{n,1}< 1\\
	&x_n \T{ ha O.C. } p 
	\definizione{ \=} 
	\limn E_{n,p} = l \neq 0,\;\;l\in \R,\;\;p\ge 1\\
	&x_n\T{ e' superlineare } \definizione{\=} 
	\limn E_{n,1}=0
	}
\end{defn}
\def\N{{\mathbb{N}}}
\begin{prop}\label{ordineconvergenzapuntofisso}
	Sia \begin{enumerate}
		\item 
	$\f:[a,b]\longrightarrow \R$
\item $x_0\in [a,b]$, $x_{k+1}=\f(x_k)\in [a,b]$
\item $x_k\to \a\in [a,b]$, $\a=\f(\a)$
\item $\f$ derivabile $n$ volte, e sia
	\eal{&k=\min\pgra{k\in \N \;|\;\f^{(k)}(\a) \neq 0}}
	con $1<k\le n$
\item $\f^{(k)}(x)$ continua in $\a$
	\end{enumerate}
	Si ha
	\eal{&
	x_n\T{ ha ordine di convergenza } k
	}
	Inoltre, se $k=1$,
	\eal{&|\f'(\a)|<1,\;k=1 \>  x_n\T{ ha ordine di convergenza } 1
	}
\end{prop}
\begin{proof}
	Per la formula di Taylor con il resto di Lagrange (vedi \AII{Taylor})
	si ha:
	\eal{&
	\T{dato }x_n\in [a,b]\setminus \pgra{\a}\;\exists 
	\xi_n\in ]\min\pgra{x_n,\a},\;\max\pgra{x_n,\a}[\T{ tale che }\\
	&\;\;
	\f(x_n)=\f(\a)+\frac{\f'(\a)}{1!}(x_n-\a)+\dots+\frac{\derivn{k-1}{\f(\a)}}{(k-1)!}(x_n-\a)^{k-1}+
\frac{\derivn{k}{\f(\xi_n)}}{k!}(x_n-\a)^{k}
	}
ma per Hp tutte le derivate di ordine $<k$ sono nulle in $\a$, quindi
\eal{&\f(x_n)=\f(\a)+\frac{\derivn{k}{\f(\xi_n)}}{k!}(x_n-\a)^{k} \= \\
&\=
\frac{\f(x_n)-\f(\a)}{(x_n-\a)^{k}} = \frac{\derivn{k}{\f(\xi_n)}}{k!}
\=\\
&\= 
\frac{x_{n+1}-\a}{(x_n-\a)^{k}} = \frac{\derivn{k}{\f(\xi_n)}}{k!}
\> \frac{|x_{n+1}-\a|}{|x_n-\a|^k}  = \frac{|\f^{(k)}(\xi_n)|}{k!}
}
Prendendo i limiti abbiamo
\eal{&\sist{x_n\to \a \\
\xi_n\in ]\min\pgra{x_n,\a},\;\max\pgra{x_n,\a}[
}  \xi_n\to \a\\
&\limn \frac{|x_{n+1}-\a|}{|x_n-\a|^k}  =  \limn \frac{|\f^{(k)}(\xi_n)|}{k!}
\ubrace{=}{\f^{(k)}\T{ continua in }\xi_n,\;\;\AII{fcontinuasuccsm}} 
\frac{|\f^{(k)}(\a)|}{k!}  \neq 0
}
Quindi, se $k>1$ la successione ha O.C. $p$.\\
Supponiamo che $k=1$, con $|\f'(\a)|<1$ allora
\eal{&0<|\f'(\a)|<1\;\;(1)\\
&\limn \frac{|x_{n+1}-\a|}{|x_n-\a|^k}  = |\f'(\a)| <1 
}
e quindi $x_n$ ha ordine di convergenza $1$.
\end{proof}
\begin{prop}
	Poniamoci nelle ipotesi della prop \see{metodonewton}, e supponiamo
	che $\exists f'''(\a)$. Allora, 
l'ordine di convergenza della successione $x_n$ del metodo di Newton e' $2$.
\end{prop}
\begin{proof}
	Adoperiamo la prop \see{ordineconvergenzapuntofisso}.
	Nel caso del metodo di Newton $\f$ e' la funzione
	\eal{&\f(x)=x-\frac{f(x)}{f'(x)}
	}
	Ricordiamo che nelle Hp della prop \see{metodonewton}, $\f''(x),\f'(x)$ non sono mai nulle.\\
	Calcoliamo le derivate di $\f$:
	\eal{&\f'(x)=f(x)\frac{f''(x)}{f'(x)^2}\\
	&\f'(\a) \ubrace{=}{f(\a)=0} 0\\
	&\f''(x) = \frac{f''(x)}{f'(x)}
	+f(x)\pton{-2\frac{(f''(x))^2}{(f'(x))^3}+\frac{f'''(x)}{(f'(x))^2}}\\
	&\f''(\a)= \frac{f''(\a)}{f'(\a)}   \neq 0
	}
\end{proof}
\begin{prop}
Nel caso migliore, il metodo delle secanti (\vedi{metodosecanti}) ha ordine $p=\frac{1+\sqrt{5}}{2}$. 
	\eal{&p^2-p-1=0\\
	&1<p<2
	}
\end{prop}
\subsubsection{Criteri di arresto}
\def\f{{\varphi}}
\def\a{{\alpha}}
\begin{defn}
	In generale, un criterio di arresto e' una condizione $P$ tale che
	\eal{&P\T{ vera } \> \T{errore} < \eps  }
	dove $\eps $ e' la precisione di macchina.
\end{defn}
\begin{prop}
	Sia $x_{n+1}=\f(x_n)$, allora come criterio di arresto possiamo
	possiamo utilizzare la seguente condizione:
	\eal{&|x_{n+1}-x_n| < \eps}
	Non sempre pero' tale criterio e' soddisfacente, infatti, anche se
	$x_n\to \a$, con $\f(\a)=\a$, potrebbe accadere che 
	$|x_{n+1}-x_n|\to \8$ oppure che $|e_n|=|x_n-\a| >  \eps$.\\

	Se la successione $x_n$ viene usata per la ricerca di uno zero di
	$f(x)$  (come nel caso del metodo di Newton), allora un altro criterio
	e'
	\eal{&|f(x_n)|<\eps }
	Anche questo criterio puo' non funzionare a dovere, infatti, anche se
	$|f(x_n)|<\eps $ potrebbe accadere che $|e_n| = |x_n-\a| > \eps$,
	oppure  $|f(x_n)| >\eps $ e $|e_n|<\eps $.
	Nel secondo caso il metodo non si arresta, anche se potrebbe, e quindi
	compira' calcoli superflui.
\end{prop}
\begin{prop}
	Metodo di Aitken.\\
	Consideriamo la successione $x_n=\f(x_{n-1})$ che converge
	linearmente al punto fisso $\a=\f(\a)$. 
Supponiamo che $\f'(\a) \neq 0,\;x_{n} \neq \a\;\;\forall n$, allora vale il
seguente criterio
di arresto:
\eal{&\pass{x_n- \frac{x_{n+1}x_{n-1}-x_{n}^2}{x_{n+1}+x_{n-1}-2x_n}
} <\eps 
}
se la condizione e' verificata, il metodo ritornera' $x_{n+1}$.
\end{prop}
\begin{proof}
	Per la formula di Taylor con il resto di Lagrange (vedi \AII{Taylor})
	si ha:
	\eal{&
	\T{dato } x_n\in [a,b]\setminus \pgra{\a}\;\exists 
	\xi_n\in ]\min\pgra{x_n,\a},\;\max\pgra{x_n,\a}[\T{ tale che }\\
	&\;\;
	\f(x_n)=\f(\a)+\frac{\f'(\a)}{1!}(x_n-\a)+\frac{\derivn{2}{\f(\xi_n)}}{2!}(x_n-\a)^{2}
	\=\\
	&\=  x_{n+1} -\a=
	\frac{\f'(\a)}{1!}(x_n-\a)+\frac{\derivn{2}{\f(\xi_n)}}{2!}(x_n-\a)^{2}\;\;(1)
	}
Allo stesso modo:
\eal{&x_{n} -\a=
\frac{\f'(\a)}{1!}(x_{n-1}-\a)+\frac{\derivn{2}{\f(\xi_{n-1})}}{2!}(x_{n-1}-\a)^{2}\;\
(2)
}
\def\b{{\beta}}
Poiche' $x_n-\a\to 0$, per $n$ sufficientemente grande, possiamo trascurare il
resto nella formula di Taylor, ottenendo il sistema:
\eal{&
\sist{ x_{n+1} -\a\approx
        \f'(\a)(x_n-\a)\\
	x_{n} -\a\approx\f'(\a)(x_{n-1}-\a)
}\;\;(3)
}
Per Hp abbiamo che $\f'(\a) \neq 0,\;x_{n} \neq \a\;\;\forall n$, quindi
\eal{&(3)\ubrace{\>}{\T{dividendo membro a membro }} 
	\frac{x_{n+1} -\a}{x_{n} -\a}\approx \frac{x_n-\a}{x_{n-1}-\a}
	\= (x_{n+1} -\a)(x_{n-1}-\a) \approx (x_n-\a)(x_{n} -\a) 
	\> \\
	&\>
	\alpha \approx
	\frac{x_{n+1}x_{n-1}-x_{n}^2}{x_{n+1}+x_{n-1}-2x_n}=\alpha'
}
abbiamo cosi' ottenuto una approssimazione $\a'$ di $\alpha$, migliore di
$x_{n}$. \\
\dots DA CONTINUARE\dots
%TODO
\end{proof}
\subsection{Sistemi non lineari}
\begin{prop}
	Sia $X\( \R^m$ e sia 
	\eal{&f:X \longrightarrow  \R^m\\
	&f(x)=(f_1(x),\dots,f_m(x))\\
	&f_i:\R^m \longrightarrow  \R
	}
	Risolvere $f(x)=\vz$ equivale a risolvere il sistema
	\eal{&\sist{
	f_1(x_1,\dots,x_m)=0\\
	f_2(x_1,\dots,x_m)=0\\
	\dots\\
	f_m(x_1,\dots,x_m)=0
	}
	}
	Supponendo $f\in \C^2(X)$ la generalizzazione del metodo di Newton diventa:
\eal{&n:=0\\
&\While:\\
&\qq J(x^{(n)})\Delta x=-f(x^{(n)})\qq \T{ sistema lineare nell'incognita
}\Delta x\\
&\qq x^{(n+1)}=\Delta x+x^{(n)}\\
&\qq n:=n+1\\
&\qq \Se \norm{\Delta x} <\eps \\
&\qq \qq \T{ la soluzione approssimata con errore $<\eps $ e' } x^{(n+1)}\\
&\qq \qq \textbf{break}
}
dove
\eal{&J(x)\T{ e' la matrice Jacobiana di $f$ calcolata in $x$ }:\\
&\qq J_{ij}(x)=\pton{\frac{\partial f_i}{\partial x_j}}_x\;\;\forall
i,j=1,\dots,m\\
}
\end{prop}
\begin{proof}
	\def\x#1{{x^{(#1)}}}
Enunciamo solo la struttura della dimostrazione.\\

Sia $\a\in X:\;f(\a)=\vz$. 
Utilizziamo la formula di Taylor generalizzata:
\eal{&f(\a) = f(\x n)+f'(\x n)(\a-\x n)+\frac{1}{2}\TRC (\a-\x
n)f''(\xi^{(n)})(\a-\x n)\\
&\T{ dove }\\
&\qq f'(\x n)=J(\x n)\\
&\qq f_{ijk}''(\xi^{(n)}) = \pton{\frac{\partial^2 f_i}{\partial x_j\partial
x_k}}_{\xi^{(n)}} \\
}
(nota\footnote{$f_{ijk}''\in \R^{m\*m\*m}$ e' una matrice a tre dimensioni. In
generale, se $v\in \R^{m_3\*1}$ e' un vettore colonna e $A\in
\R^{m_1\*m_2\*m_3}$ e' una matrice a tre dimensioni, $A_i$ sara' la $i$-esima
matrice $m_2\*m_3$ di $A$, $Av$ sara' una matrice $m_1\*m_2$, la cui riga
$i$-esima e' $A_iv$.})
e trascuriamo il resto poiche' e' un termine quadratico:
\eal{&f(\a) \approx f(\x n)+f'(\x n)(\a-\x n)
}
Poiche'
$f'(\x n)=J(\x n)$ e $f(\a)=0$ abbiamo:
\eal{&0\approx f(\x n)+f'(\x n)(\a-\x n)
}
Ponendo $\Delta x=\a-\x n$, abbiamo cosi' un sistema lineare. La cui soluzione
dara'  la seguente approssimazione:
\eal{&\a-\x n \approx \Delta x\\
&\a \approx \Delta x + \x n
}
Quindi poniamo $\x {n+1}=\Delta x + \x n$ e reiteriamo.
\end{proof}

\subsection{Massimi e minimi}
Per trovare il minimo di una funzione $f$ con derivata continua possiamo usare i
metodi forniti dall'analisi, che consistono principalmente nel trovare gli
zeri di $f'$. Per trovare gli zeri possiamo usare i metodi visti in
\see{Equazioni non lineari}.\\
In questo paragrafo vedremo dei metodi piu' generali che si possono applicare
anche a funzioni non derivabili. 

\def\x{{x_*}}
\begin{prop}
	Metodo della sezione aurea.\\
	Sia $f:[a,b]\longrightarrow \R$ (nota\footnote{non stiamo richiedendo
	che $f$ sia continua}) e unimodale, ovvero,
	\eal{&\exists \x\in [a,b]:\;\sist{f\T{ e' strettamente decrescente in
	}[a,\x]\\
	f\T{ e' strettamente crescente in }[\x,b]}}
	allora il seguente algoritmo restituisce il minimo di $f$ con un
	errore inferiore a $\eps$:
\eal{
&\While\\
&\qq x_1:=a+(1-r)(b-a)\\
&\qq x_2:=a+r(b-a)\\
&\qq \Se f(x_1)>f(x_2):\\
&\qq \qq a:=x_1\\
&\qq \textbf{Altrimenti: }\\
&\qq \qq b:=x_2\\
&\qq \Se b-a < \eps \\
&\qq \qq x_*:=a\\
&\qq \qq \textbf{break}
}
dove $r\in ]\frac{1}{2},1[$.\\
Come $r$ possiamo scegliere la sezione aurea, ovvero la soluzione positiva
dell'equazione:
\eal{&p^2+p-1=0\\
&p=\frac{-1+\sqrt{5}}{2}}
Cosi' facendo, nella  $k+1$-esima iterazione potremmo usare un $x_1$ o $x_2$
precedente e calcolare solo un nuovo $x_1'$ o $x_2'$, ad esempio:
$x_1'=x_1,\;x_2=a+r(b-a)$
\end{prop}
\begin{proof}
Supponiamo che $\x \neq a,\;\x \neq b$, allora presi due punti distinti
$x_1,x_2\in [a,b]$, con $x_1<x_2$,  
abbiamo
\step{}{$f(x_1) < f(x_2) \> \x\in [a,x_2]$ }
\begin{prova}
Se per assurdo $\x\in ]x_2, b]$, allora
\eal{&x_1<x_2 < \x  \ubrace{\>}{f\T{ decrescente in }[a,\x]}
\> f(x_1) > f(x_2)\T{ assurdo }
}
\end{prova}
Analogamente
\step{}{$f(x_1) > f(x_2) \> \x\in [x_1,b]$ }
\begin{prova}
Se per assurdo $\x\in [a,x_1[$, allora
\eal{&\x < x_1<x_2   \ubrace{\>}{f\T{ crescente in }[\x,\b]}
\> f(x_1) < f(x_2)\T{ assurdo }
}
\end{prova}
Quindi, prendendo due punti in $[a,b]$ sappiamo decidere in quale
sottointervallo si trova il minimo. A questo punto, bastera' prendere due
nuovi punti in questo sottointervallo e ripetere la procedura.\\
Sceglieremo in modo opportuno i punti $x_1,x_2$:
\eal{&x_1=a+(1-r)(b-a)=b-r(b-a),\;\;x_2=a+r(b-a)\\
&\T{ con }r\in  ]\frac{1}{2},1[\\
&a < x_1<\frac{a+b}{2}< x_2 < b, \T{ infatti }\\
&\qq 0 < (1-r)(b-a) < \frac{b-a}{2} < r(b-a) < b-a\\
&\qq 0 < 1-r< \frac{1}{2} < r < 1\\
&\qq \sist{0 < 1-r< \frac{1}{2} \\
\frac{1}{2} < r < 1} \= \sist{0 < \frac{1}{2} < r\\
\frac{1}{2} < r < 1}\T{ vera}
}
I due possibili sottointervalli sono:
\eal{&[a,x_2],\;[x_1,b]
}
ed hanno la stessa ampiezza:
\eal{&x_2-a=b-x_1
\= r(b-a) = b-a-(1-r)(b-a)= r(b-a)  \= 0=0
}
Come $r$ possiamo scegliere la sezione aurea:
$r=\frac{-1+\sqrt{5}}{2}$.\\
Sia $[a_k,b_k]$ l'intervallo della $k$-esima iterazione,
\eal{
&\T{Per induzione, si ha che l'ampiezza dell'intervallo e': }r^k(b-a)\;\;(1)\\
&\x\in [a_k,b_k] \> |e_k|=|\x-a_k| \le |b_k-a_k|  \ubrace{=}{(1)} r^k(b-a)
\;\;(1.1)
}
e poiche' $0<r<1$, per $k\to 0$ la $(1)$ converge a $0$, e quindi $a_k\to
\x$.\\
Dalla $(1.1)$ possiamo ricavare anche il seguente criterio di arresto:
\eal{&|b_k-a_k| < \eps 
}
Supponiamo che il nuovo intervallo sia $[a,x_2]$, cioe' $a'=a,\;b'=x_2$. Se
vogliamo risparmiare il calcolo di un punto nella nuova suddivisione,
imponiamo che
\eal{&x_2'=x_1\=a'+r(b'-a')=a+(1-r)(b-a)\=
r(x_2-a)=(1-r)(b-a) \=\NN
\ubrace{\=}{\T{sostituendo }x_2} 
r(r(b-a))=(1-r)(b-a)\= r^2=1-r}
\end{proof}
\begin{prop}
	Metodo della parabola.\\
	Si interpola la funzione $f$ in tre punti, ottenendo cosi una
	parabola. Il minimo della parabola sara' una approssimazione del
	minimo di $f$.\\

	Questo metodo puo' essere usato in congiunzione al metodo della
	sezione aurea.
\end{prop}

\section{Integrali}
\begin{defn}\ilabel{formula di quadratura}
Data la funzione peso $w:[a,b]\longrightarrow \R$, con $w(x) > 0\;\;\forall x \in
[a,b]\-\pgra{z_1,\dots,z_s}$,\;$w(z_i)=0\;\;\forall i=1,\dots,s$, definiamo
l'integrale pesato:
\eal{&I:\sczn{0}{[a,b]}\longrightarrow \R\\
&I(f) = \intd{a}{b} w(x)f(x)\;dx
}

Scelti $n+1$ nodi $x_i\in [a,b]\;\;\forall i =0,\dots,n$, con 
$x_0<x_1<\dots<x_n$, e scelti $n+1$ pesi $w_i\in
\R\;\;\forall i=0,\dots,n$, chiameremo \textrm{formula di quadratura}
la seguente funzione:
\eal{&I_n:\sczn{0}{[a,b]}\longrightarrow \R\\
&I_n(f) = \sumzin w_if(x_i)
}
\end{defn}
\begin{prop}
Dalla proprieta' dell'integrale definito segue che $I$ e' una funzione
lineare, ovvero prese $f,g\in \sczero{[a,b]}, \alpha,\beta\in \R$, si
	ha
	\eal{&I(\alpha f+\beta g) = \alpha I(f) + \beta I(g)}
Anche $I_n$ e' una funzione lineare.
\end{prop}
\begin{defn}\label{normadiFsuczero}
	Sia data $F:\sczero{[a,b]}\longrightarrow \R$, allora definiamo la
	norma di $F$:
	\eal{&\norm{F}\definizione{=} \sup\pgra{|F(f)|\;|\;f\in
	\sczero{[a,b]},\;\;\norm{f}=1}\\
	&\T{dove }\\
	&\qq \norm{f}=\max_{x\in[a,b]}|f(x)|
	}
	si verifica che la funzione appena definita e' una norma e gode delle
	seguenti proprieta':
\eal{&1.\;\;\norm{F}=\max\pgra{|F(f)|\;|\;f\in\sczero{[a,b]},\;\;\norm{f}=1}\\
&2.\;\;|F(f)|\le \norm{F}\norm{f}
}
\end{defn}

\begin{prop}\label{normediIeIn}
\eal{&1.\;\;\norm{I} = \intd{a}{b} w(x)\;dx\\
&2.\;\;\norm{I_n}=\sumzin |w_i|
}
\end{prop}
\begin{proof}
Sia $f\in \sczero{[a,b]}$ t.c. $\norm{f}=1$,
\eal{&\norm{f}=\max_{x\in[a,b]}|f(x)|=1 \> |f(x)|\le 1\;\;\forall x\in
[a,b]\;\;(1)}
	\step{}{Dim $1.$}
	\begin{prova}
\eal{
		&|I(f)|=\pass{\intd{a}{b}w(x)f(x)\;dx}
		\le \intd{a}{b} |w(x) | |f(x)| \;dx=
		\ubrace{=}{w(x)\ge 0\;\forall x}   \intd{a}{b} w(x) |f(x)| \;dx
		\ubrace{\le}{(1)} \intd{a}{b} w(x) \;dx  \\
		&|I(f)|\le \intd{a}{b} w(x) \;dx\;\;\forall f:\;\norm{f}=1\>
		\norm{I}=\sup_{\norm{f}=1}|I(f)| \le \intd{a}{b} w(x)\;dx\;\;(2)\\
		&|I(1)|= 
		\pass{\intd{a}{b}w(x)\;dx} =
		\intd{a}{b}w(x)\;dx\\
		&|I(1)| \le \sup_{\norm{f}=1}|I(f)|=\norm{I}\\
		&\qq \> \intd{a}{b}w(x)\;dx \le  \norm{I}\;\;(3)\\
		&(2),\;(3) \> \norm{I}= \intd{a}{b}w(x)\;dx 
		}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
Sia $f\in \sczero{[a,b]}$ t.c. $\norm{f}=1$, 
\eal{&
|I_n(f)|=\pass{\sumzin w_if(x_i)} \le  \sumzin |w_i| |f(x_i)| 
\ubrace{\le }{(1)} \sumzin |w_i|\\
&|I_n(f)|\le \sumzin |w_i|\;\;\forall f:\;\norm{f}=1\>
\norm{I_n} \le  \sumzin |w_i|\;\;(4)
}
Poiche' $x_0<x_1<\dots<x_n$, possiamo definire la seguente funzione:
\eal{&g(x)=\sist{1&x=x_i,\;w_i\ge 0\\
		-1&x=x_i,\;w_i<0\\
		g(x_{i-1})+\frac{g(x_i)-g(x_{i-1})}{x_i-x_{i-1}}(x-x_{i-1})
		&x\in ]x_{i-1},x_{i}[
}\\
&|g(x)|\le 1\;\;\forall x\in [a,b],\T{ infatti, }\\
&\qq |g(x_i)|=1\\
&\qq \T{Sia }x\in ]x_{i-1},x_i[\-\pqua{x_0,\dots,x_n}\\
&\qq x\in ]x_{i-1},x_i[ \> 0< x-x_{i-1} < x_i-x_{i-1} \>
 0< \frac{x-x_{i-1}}{x_i-x_{i-1}}< 1\;\;(5)\\
&\qq
|g(x)|=\pass{g(x_{i-1})+\frac{g(x_i)-g(x_{i-1})}{x_i-x_{i-1}}(x-x_{i-1})}\\
&\qq \qq \T{Se } g(x_i)=g(x_{i-1})=\pm 1\T{ allora} |g(x)|=|g(x_{i-1})| = 1\\
&\qq\qq \T{Se } g(x_i)=-1,\;g(x_{i-1})=1\T{ allora} \\
&\qq\qq \qq 1\ubrace{>}{(5)}g(x) = 1-2\frac{x-x_{i-1}}{x_i-x_{i-1}}
\ubrace{>}{(5)} 1-2=-1  \> -1<g(x)<1 \= |g(x)|<1\\
&\qq\qq\T{Analogamente se } g(x_i)=1,\;g(x_{i-1})=-1 \T{ si ha } |g(x)|<1
}
Si verifica facilmente che $g(x)$ e' una funzione continua in $[a,b]$.
Nota\footnote{In pratica, $g(x)$ e' una spezzata che unisce i punti 
$\pton{x_i,g(x_i)}$}
Quindi,
\eal{&|I_n(g)|=\pass{\sumzin w_ig(x_i)} 
\ubrace{=}{\T{per costruz. di }g}  \sumzin |w_i| \\
&|I_n(g)| \le \norm{I_n}\\
&\qq \> \sumzin |w_i|\le \norm{I_n}\;\;(6)\\
&(4),(6) \> \norm{I_n} = \sumzin |w_i|
}
\end{prova}
\end{proof}
\def\l{{\lambda}}
\begin{defn}\ilabel{formula quadratura interpolatoria}
	Sia $I_n:\sczero{[a,b]}\longrightarrow \R$ una formula di quadratura,
\eal{&I_n\T{ e' una formula interpolatoria } \definizione{\=}
I_n(f)=I(L_n(f))\;\;\forall f\in \sczero{[a,b]}}
dove $L_n$ e' il polinomio che interpola $f$ negli $n+1$ nodi di $I_n$.
\end{defn}
\begin{prop}\label{formulaquadraturainterpolatoria}
Sia $I_n$ una formula di quadratura interpolatoria. Si ha 
\eal{
&|I(f)-I_n(f)| \le
\norm{f-L_n}   
\intd{a}{b}w(x)\;dx
}
Inoltre, i pesi di $I_n$ sono dati da:
\eal{&w_j=\intd{a}{b} w(x)\l_j(x)\;dx\;\;\forall j=0,\dots,n\\
&\T{dove } \l_j(x)\T{ e' dato dalla forma di Lagrange (\vedi{formalagrange})
}
}
ovvero, \eal{&
I_n(f)=\sumzjn w_jf(x_j)
}
\end{prop}
\begin{proof}
Per semplicita' con $L_n(x)$ indichiamo $L_n(f)(x)$.
	Abbiamo:
	\eal{
&|I(f)-I_n(f)| =
\pass{\intd{a}{b}w(x)f(x)\;dx -\intd{a}{b} w(x)L_n(x)\;dx } 
= \pass{\intd{a}{b}w(x)(f(x)-L_n(x))\;dx} \le \\
&
\le \intd{a}{b} |w(x)| |f(x)- L_n(x)|\;dx \ubrace{=}{w(x)\ge 0\;\;\forall x}
\intd{a}{b} w(x) |f(x)- L_n(x)|\;dx\le \\
&
\ubrace{\le}{|f(x)- L_n(x)|\le \norm{f-Ln} \;\;\forall x} 
\intd{a}{b} w(x) \norm{f- L_n}\;dx = \norm{f-L_n} \intd{a}{b} w(x) \;dx 
}
Usando la forma di Lagrange (\vedi{formalagrange}) abbiamo:
\eal{
&\l_j(x) =\prod_{0\le i\le n,\;\;i \neq j} \frac{x-x_i}{x_j-x_i}\\
&L_n(x)=\sumzjn f(x_j)\l_j(x)\\
&I_n(f)=I(L_n)=\intd{a}{b} w(x)L_n(x)\;dx=\intd{a}{b} w(x)\sumzjn f(x_j)\l_j(x) \;dx=\sumzjn
f(x_j)\intd{a}{b} w(x) \l_j(x)\;dx 
= \sumzjn w_jf(x_j) 
}
\end{proof}
\begin{defn}
Sia data una formula di quadratura $I_n:\sczero{[a,b]}\longrightarrow \R$, 
\eal{&I_n\T{ ha ordine polinomiale }m \definizione{\=} m=\max\pgra{s\in
\N\;|\;I(p)=I_n(p),\;p\in \R[x]_{s}}
}
(Nota\footnote{Ricordiamo che $R[x]_{s}$ e' l'insieme dei polinomi di $\R[x]$
aventi grado $\le s$})
Per indicare che $I_n$ ha ordine polinomiale $m$ useremo la notazione
\eal{&\deg I_n = m}
\end{defn}
\begin{exemp}
	Sia $w(x)\equiv 1$
	\ilabel{formula trapezi}
	\ilabel{formula Simpson}
	\begin{enumerate}
		\item 
	La formula dei trapezi:
	\eal{&T(f)\definizione{=}\frac{f(a)+f(b)}{2}(b-a)}
	ha ordine polinomiale $1$. Infatti, se $f$ e' una retta, allora e'
	$T(f)$ e' proprio l'area sottesa da tale retta.
	Il resto e':
	\eal{&R=I(f)-T(f)=-\frac{(b-a)^3}{12}f''(\xi),\;\;\T{ per qualche }\xi\in[a,b]}
\item La formula del punto medio:
	\eal{&M(f) \definizione{=} (b-a)f\pton{\frac{b+a}{2}}}
	ha ordine polinomiale $1$. Basta notare che l'area calcolata da $M(f)$
 e' uguale all'area del trapezio calcolata da $T(f)$
 \item La formula di Cavalieri-Simpson: si ottiene interpolando $f$ nei punti
	 punti $(a,f(a)),(b,f(b)),(m,f(m))$, con
	 $m=\frac{a+b}{2}$. Ovvero, se $L_n$ e' il polinomio interpolatore di
	 $f$, 
	 \eal{&S(f) \definizione{=} I(L_n)= \frac{b-a}{6}\pqua{f(a)+4f\pton{\frac{a+b}{2}}+f(b)}
	 }
	 $S(f)$ ha ordine $\ge 2$, infatti, se $p\in \R[x]$ e' di grado due, 
per l'unicita' dell'interpolazione 
(\vedi{esisteunicasolinterpolpolinom}) si ha $L_n=p$ e quindi 
$S(p)=I(L_n)=I(p)$.
	\end{enumerate}
\end{exemp}

\begin{prop}\label{formulainterpolatssedegIngen}
	\eal{&I_n\T{ e' una formula interpolatoria }\=
\deg I_n \ge n
	}
\end{prop}
\begin{proof}
Sia $m=\deg I_n$
	\step{}{Dim $\>$}
	\begin{prova}
		\eal{&\T{Sia }f(x) \in \R[x]_{n}\\
		&\T{Per l'unicita' dell'interpolazione
		(\vedi{esisteunicasolinterpolpolinom}) abbiamo }L_n(p)
		=p\\
		&I_n(p) \ubrace{=}{\T{$I_n$ e' una form.
		interp.}}I( L_n(p)) =I(p)\\
		&I_n(p)=I(p)\;\;\forall p \in \R[x]_n
		\ubrace{\>}{\T{def. di ordine
                polinom.}} m\ge n
		}
	\end{prova}
	\step{}{Dim $\<$}
	\begin{prova}
\def\l{{\lambda}}
Siano $\lambda_i(x)$ i polinomi di grado $n$ di Lagrange
(\vedi{formalagrange})
\eal{&I(\l_i) \ubrace{=}{\deg I_n=m \ge n=\deg\l_i} I_n(\l_i)
= \sumzjn w_j\l_i(x_j)  \ubrace{=}{\l_i(x_j)=\delta_{ji}} w_i\\
&I_n(f) = \sumzjn w_jf(x_j) = \sumzjn I(\l_j)f(x_j)  \ubrace{=}{
\T{linearita'}} I\pton{\sumzjn \l_j(x)f(x_j)}  \ubrace{=}{\see{formalagrange}} 
I(L_n(f))\\
&I_n(f)=I(L_n(f))\;\;\forall f \in \sczero{[a,b]}\> I_n\T{ e' interpolatoria}
}
	\end{prova}
\end{proof}
\begin{prop}
	Sia $I_n$ una formula interpolatoria. Conoscendo i nodi
	$x_i,\;i=0,\dots,n$ si possono calcolare i pesi risolvendo il seguente
	sistema $n+1\*n+1$:
	\eal{&\intd{a}{b}w(x)x^i\;dx=\sumzjn w_jx_j^i\;\;i=0,\dots,n}
	nelle incognite $w_j\;\;j=0,\dots,n$.
\end{prop}
\begin{proof}
	Per la prop \see{formulainterpolatssedegIngen} si ha $\deg I_n\ge n$,
	quindi $I_n$ e' esatta per i polinomi di grado $\le n$, quindi
	\eal{&I(x^i)=I_n(x^i) \;\;\forall i=0,\dots,n
	\= \intd{a}{b}w(x)x^i\;dx=\sumzjn w_jx_j^i\;\;i=0,\dots,n
	}
\end{proof}

\begin{thm}\label{thmconvergenzadiIn}
Sia
\begin{enumerate}
	\item $f\in \sczero{[a,b]}$
	\item $\pgra{I_n}$ una successione di formule di quadratura qualsiasi
	\item $\limn \deg I_n =\8$
	\item $\exists M>0:\;\norm{I_n} \le M\;\;\forall n\ge 0$
\end{enumerate}
allora
\eal{&\limn I_n(f) = I(f)
}
\end{thm}
\begin{proof}
\def\f{{\varphi}}
Sia $m_{n} =  \deg I_n$.
Sia $\f_{m_n} \in \R[x]_{m_n}$ il polinomio dato dal thm \see{thmweierstrasII},
relativamente alla funzione $f$.\\
\eal{
&\deg \f_{m_n}\le m_n=  \deg I_n \> I(\f_{m_n})=I_n(\f_{m_n})\\
&|I_n(f)-I(f)| = |I_n(f)-I_n(\f_{m_n})+I(\f_{m_n})-I(f)|
\le |I_n(f)-I_n(\f_{m_n})| + |I(\f_{m_n})-I(f)|=\\
&
\ubrace{=}{\T{linearita'}} 
|I_n(f-\f_{m_n})| + |I(\f_{m_n}-f)|
\ubrace{\le }{\see{normadiFsuczero}}
\norm{I_n}\norm{f-\f_{m_n}}+
\norm{I}\norm{f-\f_{m_n}}
= \norm{f-\f_{m_n}} \pton{\norm{I}+
\norm{I_n}}\;\;(1)\\
&\limn m_{n}= \limn \deg I_n =\8  \ubrace{\>}{\see{thmweierstrasII}}  \limn
\f_{m_n} = f \> \limn \norm{f-\f_{m_n}} =0\;\;(2)\\
&\T{Per Hp la successione }\norm{I_n} \T{ e' limitata },\;\;
\norm{I}\in \R \> \norm{I}+
\norm{I_n}\T{ e' limitata} \;\;(3)\\
&(1),(2),(3) \> \limn |I_n(f)-I(f)| \le \limn\norm{f-\f_{m_n}} \pton{\norm{I}+
\norm{I_n}} =0 \> \limn I_n(f)=I(f)
}
\end{proof}
\def\a{{\alpha}}
\def\b{{\beta}}
\begin{prop}Calcolo pratico di $I_n$.\\
	\label{calcoloInperpiufunzioni}
	Consideriamo una formula di quadratura
	$I_n:\sczero{[a,b]}\longrightarrow \R$ che approsimi bene la funzione
	$I$.\\
Per il calcolo di $I_n(f_i),\;\;f_i\in\sczero{[a,b]} \;\forall i=1,\dots,m$, si puo' adottare il seguente
algoritmo:
\begin{enumerate}
	\item Si sceglie un intervallo $[\a,\b]\([a,b]$ conveniente (ad
		esempio $[0,1]$).
	\item Si scelgono $n+1$ nodi in $[\a,\b]$.
	\item Si pre-computano i pesi $w_i$ relativamente all'intervallo
		$[\a,\b]$. Questo e' il calcolo piu' pesante, in quanto
		richiede il calcolo di $\intd{\a}{\b}w(x)$.\\
		Nota: per una formula interpolatoria, i pesi $w_i$ dipendono
		solo dai nodi (\vedi{formulaquadraturainterpolatoria})
	\item Per il calcolo di $I_n(f_i)$:
		\begin{enumerate}
			\item Si calcolano i nuovi pesi e nodi:
				\eal{&
w_j'=w_j \frac{b-a}{\b-\a}\\
&x_j'=\frac{b-a}{\b-\a}(x_j-\a)+a}
			\item Si ha la seguente approssimazione:
			\eal{&I_n(f_i)\approx \sumzjn w_j'f_i(x_j')
				}
		\end{enumerate}
\end{enumerate}
\end{prop}
\begin{proof}
	Per ipotesi:
\eal{&\intd{\a}{\b} f(\xi)\;d\xi \approx I_n(f) = \sumzjn w_jf(x_j)\;\;(1) }
Sia $f=f_i$.
Effettuiamo il seguente cambio di variabili:
\def\f{{\varphi}}
\eal{&x=\f(\xi)=\frac{b-a}{\b-\a}(\xi-\a)+a,\;\;\xi\in [\a,\b],\;\;x\in[a,b]\\
&\qq\T{in pratica stiamo mappando l'intevallo $[\a,\b]$ in $[a,b]$},\;
\T{ imponendo che } \xi-\a:\beta-\a=x-a:b-a\\
&\inv \f(x)= \frac{\b-\a}{b-a}(x-a)+\a\\
&\intd{a}{b} f(x)\;dx 
= \intd{\inv \f(a)}{\inv \f(b)}\f'(\xi) f(\f(\xi))\;d\xi =\\
&
= \intd{\a}{\b}\frac{b-a}{\b-\a} f\pton{\frac{b-a}{\b-\a}(\xi-\a)+a}\;d\xi
\ubrace{\approx}{(1)} I_n\pton{\frac{b-a}{\b-\a} f\pton{\frac{b-a}{\b-\a}(\xi-\a)+a}
} = \\
&=\sumzjn w_j \pqua{\frac{b-a}{\b-\a}
f\pton{\frac{b-a}{\b-\a}(x_j-\a)+a}}
=\sumzjn w_j'f(x_j')
}
\end{proof}
\begin{prop}
Formule di Newton-Cotes.\\
Le formule di Newton-Cotes sono formule interpolatorie ottenute scegliendo
una distribuzione uniforme dei nodi. Si classificano in \emph{formule
chiuse} e \emph{formule aperte}
\begin{description}
	\item[Formule chiuse]
		Gli estremi $a,b$ sono dei nodi: $x_0=a,\;x_n=b$,
		\eal{&h=\frac{b-a}{n}\\
		&x_i=a+ih\;\;i=0,\dots,n
		}
	\item[Formule aperte] Gli estremi non sono dei nodi:
		\eal{&h=\frac{b-a}{n+2}\\
		&x_i=a+(i+1)h\;\;i=0,\dots,n
		}
\end{description}
\end{prop}
\begin{exemp}
	\begin{description}
		\item[Chiusa]
			Per $n=1$ si ottiene la formula del trapezio: infatti,
			stiamo interpolando la funzione in $2$ punti, ovvero
			negli estremi. Il polinomio interpolatore e' la retta
			che passa per i punti
			$(a,f(a)),(b,f(b))$. $I_n(f)$ e' l'area sottostante al
			alla retta.\\
			Analogamente, per $n=2$ si ottiene la formula di
			Simpson.
		\item[Aperta]
			Per $n=0$ si ottiene la formula del punto medio.
	\end{description}
\end{exemp}
\begin{prop}\label{nogaranziapernewton}
	Consideriamo una qualsiasi successione $\pgra{I_n}$ di formule di Newton-Cotes, allora si dimostra che 
\eal{&\limn \sumzin |w_i| = \8  \ubrace{\=}{\see{normediIeIn}} 
\limn \norm{I_n}  =\8
}
Per questo motivo, non possiamo applicare il thm \see{thmconvergenzadiIn}.
Quindi, non abbiamo alcuna garanzia sulla convergenza delle formule di
Newton-Cotes.
\end{prop}
\begin{prop}\label{errorinewtoncotes}
	Consideriamo una formula $I_n$ di Newton-Cotes. Si dimostra che
	\eal{&\deg I_n = \sist{ n &n\T{ dispari}\\
	n+1&n \T{ pari}}
	}
	Posto $R_n(f)=I(f)-I_n(f)$, chiamato \iemph{resto} della formula di
	quadratura, si dimostra che:
	\eal{
	& \textbf{$n$ pari}:\\
	&\qq R_n(f)=K\frac{f^{(n+2)}(\xi)}{(n+2)!}h^{n+3},\;\;\T{ per qualche }\xi\in
	[a,b ]\\
	&\qq K=\sist{
	\intd{-1}{n+1}xr_{n}(x)\;dx&I_n\T{ formula aperta}\\
	\intd{0}{n}xr_{n}(x)\;dx&I_n\T{ formula chiusa}
	}\\
& \textbf{$n$ dispari}:\\
	&\qq R_n(f)=K\frac{f^{(n+1)}(\xi)}{(n+1)!}h^{n+2},\;\;\T{ per qualche }\xi\in
	[a,b ]\\
	&\qq K=\sist{
	\intd{-1}{n+1}r_{n}(x)\;dx&I_n\T{ formula aperta}\\
	\intd{0}{n}r_{n}(x)\;dx&I_n\T{ formula chiusa}
	}\\
	&\T{dove }\\
	&\qq r_n(x) = \frac{x!}{(x-n-1)!} = x(x-1)(x-2)\dots(x-n)
	}
In particolare, per $n=0,\dots,4$, $R_n$ assume i seguenti valori:\\
\begin{center}
\begin{tabular}{rcc}
n & \T{Chiusa } & \T{Aperta}\\
\hline
\strut{6} 0 &  &  $\frac{1}{3} h^3 f^{(2)}(\xi)$ \\
\strut{6}
\rule{0pt}{4ex} 1 & $-\frac{1}{12} h^3 f^{(2)}(\xi)$ &  $\frac{3}{4}h^3 f^{(2)}(\xi)$ \\
\strut{6}
2 & $-\frac{1}{90} h^5 f^{(4)}(\xi)$ &  $\frac{14}{45}h^5 f^{(4)}(\xi)$ \\
\strut{6} 3 & $-\frac{3}{80} h^5 f^{(4)}(\xi)$ &  $\frac{95}{144}h^5 f^{(4)}(\xi)$ \\
\strut{6}
 4 & $-\frac{8}{945} h^7 f^{(6)}(\xi)$ & $\frac{41}{140}h^7 f^{(6)}(\xi)$ 
\end{tabular}
\end{center}
\end{prop}
\def\.{{\cdot}}
\def\R{{\mathbb{R}}}
\begin{prop}\label{degInmassimo}
	\eal{&\max \pgra{\deg I_n\;|\;I_n\T{ formula di quadratura su }n+1\T{
	pesi e nodi}}
	= 2n+1
	}
ovvero, l'ordine polinomiale massimo raggiungibile da una forma di quadratura
$I_n$ e' $2n+1$.\\
In particolare, se $I_n$ e' una formula di quadratura interpolatoria sui nodi
$x_0,\dots,x_n\in [a,b]$ e pesi $w_0,\dots,w_n$, si ha
\eal{&q_n \perp f\;\;\forall f\in \R[x]_n \> \deg I_n=2n+1\\
&\T{dove }\\
&\qq q_n(x)=\prod_{i=0}^{n}x-x_i\\
&\qq \T{Il prodotto scalare usato e': }f\.g = I(fg)\;\;\forall f,g\in
\sczero{[a,b]}
}
\end{prop}
\begin{proof}
	\step{}{
Dim. che $\deg I_n < 2n+2$ per qualsiasi scelta dei pesi e dei nodi
	}
	\begin{prova}
Dimostriamo che esiste un polinomio $p$ di grado $2n+2$ per cui $I_n(f)	 \neq
I(f)$.\\
$I_n$ e' una formula di quadratura, quindi
\eal{&I_n(f)=\sumzin w_if(x_i) 
}
Poniamo
\eal{&q(x)=\prod_{i=0}^{n}x-x_i\\
&p(x)= q(x)^2\\
&\deg q(x)= n+1,\;\;\deg p(x)=2n+2
}
si ha
\eal{&q(x_i)=p(x_i)=0\;\;\forall i=0,\dots,n\\
&I(p) = \intd{a}{b} w(x)p(x)\;dx  \ubrace{>}{
p(x),w(x)\ge 0\;\;\forall x\in [a,b],\;\;\exists \xi\in [a,b]:\;w(\xi)p(\xi)
>0,\;\;\AII{integralestrettpositivo}} 0\\
&I_n(p)= \sumzin w_ip(x_i) =0\\
&\qq \> I_n(p) \neq I(p)
}
\end{prova}
\step{}{Dim $2.$}
\begin{prova}
	Sia $f\in \R[x]_{2n+1}$. Dimostriamo che $I(f)=I_n(f)$.\\
Sia $L_n(f)$ il polinomio che interpola $f$ nei punti $x_0,\dots,x_n$. Poiche'
$I_n$ e' interpolatoria, abbiamo
\eal{&I_n(f)= I(L_n(f))
}
Per il thm \see{formadinewton} abbiamo
\eal{&f(x)  = L_n(f)(x)+ \ubrace{f[x_0,\dots,x_{n},x]}{g(x)}q_n(x)\\
&f\in \R[x]_{2n+1},\;\;q_n\in \R[x]_{n+1},\;\;L_n(f)\in \R[x]_n 
\> g(x)=f[x_0,\dots,x_{n},x] \in \R[x]_{n}\\
&q_n\perp h\;\;\forall h\in \R[x]_n \> q_n\perp g \= I(gq_n)=0\\
&I(f)=I(L_n(f))+I(gq_n)  \ubrace{=}{I(gq_n)=0} I(L_n(f)) = I_n(f)
}
\end{prova}
\end{proof}
\begin{defn}
	Sia $I_n$ una formula di quadratura,
	\eal{&I_n\T{ e' gaussiana } \definizione{\=} \deg I_n=2n+1}
\end{defn}
\begin{prop}
\ilabel{quadraturagaussiana}
Metodo per il calcolo dei nodi $x_0,\dots,x_n$ che rendono la formula
interpolatoria $I_n$ una gaussiana.\\
Sia $q_n(x)=\prod_{i=0}^{n}x-x_i$
\begin{enumerate}
	\item $q_n(x)=a_0+a_1x+\dots+x^{n+1}$ (Nota: \footnote{$q_n(x)$ e'
		monico})
	\item Si risolve il sistema  lineare $(n+1)\*(n+1)$
		\eal{&\intd{a}{b} w(x)x^kq_n(x)\;dx=0\;\;\forall k=0,\dots,n
		}
nelle incognite $a_0,\dots,a_{n}$.(Nota\footnote{Stiamo supponendo $w(x)$ si possa integrare facilmente (ad esempio, $w(x)$
puo' essere un polinomio). Poiche' $x^kq_n(x)$ e'
un polinomio, il sistema diventa lineare.})
	\item Si trovano gli zeri di $q_n(x)$. Tali zeri sono i nodi
		$x_0,\dots,x_n$ cercati.
\end{enumerate}
Nota: Per calcolare i nodi in piu' intervalli $[a_1,b_1],\dots,[a_r,b_r]$
convien pre-computare $x_0,\dots,x_n$ in un intervallo fisso (ad esempio
$[0,1]$) e usare la prop \see{calcoloInperpiufunzioni}.
\end{prop}
\begin{proof}
\eal{&\intd{a}{b} w(x)x^kq_n(x)\;dx=0 \= I(x^kq_n) =0 \= x^k\. q_n=0 \=
x^k\perp q_n\;\;\forall k=0,1,\dots,n
	}
Poiche' $1,x,\dots,x^n$ e' una base di $\R[x]_n$, si ha
\eal{&
q_n \perp x^k\;\;\forall k=0,\dots,n
\ubrace{\=}{\GII{proportobase}}  
q_n\perp f\;\;\forall f\in \R[x]_n  
}
Quindi per la prop. \see{degInmassimo} abbiamo la tesi.
\end{proof}
\begin{exemp}
	\begin{enumerate}
		\item Per $w(x)\equiv 1,\;\;[a,b]=[-1,1],\;\;\deg I_n=2n+1$,
			$I_n$ viene chiamata \iemph{formula di Gauss-Legendre}
		\item Per $w(x)\equiv \frac{1}{\sqrt{1-x^2}},\;\;[a,b]=[-1,1],\;\;\deg I_n=2n+1$,
			$I_n$ viene chiamata \iemph{formula di
			Gauss-Chebyshev}. Si ha:
			\eal{&w_i=\frac{\pi}{n+1}\;\;\forall i=0,\dots,n\\
			&\T{I nodi $x_i$ sono le radici di $t_{n+1}(x)$. Vedi
			\see{polinomioChebyshev}}
			}
	\end{enumerate}
\end{exemp}
\subsection{Formule composite}
\begin{defn}
	Suddividiamo l'intervallo $[a,b]$ in $N$ intervallini
	$[x_{i-1},x_i]\;\;i=1,\dots,N$. Possiamo allora spezzare il calcolo
	dell'integrale:
\eal{&
\intd{a}{b} f(x)\;dx=\sumiN \intd{x_{i-1}}{x_i}f(x)\;dx =
\sumiN I^{(i)}(f)\;dx \approx \sumiN I_n^{(i)}(f)
\definizione{=} C_{N}(f)
}
$C_N(f)$ si chiama formula di \iemph{quadratura composita}.\\
\end{defn}
\begin{prop}
Formule composite:
\begin{enumerate}
	\item Formula dei trapezi:
		\eal{&
		C_{N}(f) = \sumiN
		\frac{f(x_{i-1})+f(x_{i})}{2}(x_{i}-x_{i-1})}
		Se $x_{i}-x_{i-1}=h=\frac{b-a}{N}$, allora
		\eal{&
C_{N}(f)= h\pton{\frac{f(a)+f(b)}{2} + \sum_{i=1}^{N-1} f(a+ih)}
		}
\end{enumerate}
\end{prop}
\begin{proof}
	\begin{enumerate}
		\item Trapezi uniforme:
	\eal{&
		C_{N}(f) =  \sumiN
                \frac{f(x_{i-1})+f(x_{i})}{2} h
		=\frac{h}{2}\sumiN\pton{f(x_{i-1})+f(x_{i})}\\
&\sumiN\pton{f(x_{i-1})+f(x_{i})} 
= \sumiN f(x_{i-1})+\sumiN f(x_{i}) =\NN
= \sum_{i=0}^{N-1} f(x_{i})+\sumiN f(x_{i})
= f(x_0)+f(x_N)+ \sum_{i=1}^{N-1} f(x_{i})+\sum_{i=1}^{N-1} f(x_{i})
= f(x_0)+f(x_N)+ 2\sum_{i=1}^{N-1} f(x_{i})
\\
& C_{N}(f) = \frac{h}{2}\pton{ f(x_0)+f(x_N)+2\sum_{i=1}^{N-1} f(x_{i})} =
h\pton{\frac{f(x_0)+f(x_N)}{2} + \sum_{i=1}^{N-1} f(x_{i})}
}
Poiche' $x_0=a,x_N=b,x_{i}=a+ih\;\;\forall  i=0,\dots,N$, abbiamo
\eal{&
C_{N}(f)= h\pton{\frac{f(a)+f(b)}{2} + \sum_{i=1}^{N-1} f(a+ih)}
}
\end{enumerate}
\end{proof}
\begin{exemp}
	Per la formula dei trapezi composita:
	\eal{&R=-\frac{b-a}{12}h^2f''(\xi)}
	dove $[a,b]$ e' stato suddiviso uniformemente in $N$ intervallini, con
	$h=\frac{b-a}{N}$.
\end{exemp}

\begin{prop}Estrapolazione di Richardson.\\
	\label{estrapolazrichardson}
	\ilabel{estrapolazione di Richardson}
Sia $\pgra{I_n(f,h)}_{h\in \R}$ una famiglia di formule di quadratura.
Supponiamo che il resto di $I_n(f,h)$  sia del tipo:
\eal{&R_n(f,h)= c_1h^{p_1} + c_2h^{p_2} + \dots + c_kh^{p_k} + \dots\\
&p_1<p_2 <\dots < p_k<\dots
}
Scelto $q>1$, possiamo costruire la seguente successione di formule interpolatorie:
\eal{&
F_1(f,h)=I_n(f,h)\\
&F_{k+1}(f,h)=\frac{q^{p_k}F_k(f,h)-F_k(f,qh)}{q^{p_k}-1}
}
e si ha
\eal{&I(f)-F_{k+1}(f,h)  = O(h^{p_{k+1}})
}
Quindi se $h<1$, il resto di $F_{k+1}$ tende a $0$ (per $k\to \8$)
esponenzialmente. In altre parole, usando poche iterazioni
dell'estrapolazione di Richardson, miglioriamo notevolemente l'accuratezza
della formula di quadratura.\\

Il calcolo di $F_{k+1}(f,h)$ si puo' eseguire in maniera efficiente
utilizzando un metodo iterativo analogo a quello delle differenze divise
(\vedi{differenzedivisealgo}). Si puo' visualizzare l'algoritmo cosi':
	\eal{&
\begin{matrix}
F_1(f,h)   &            &               & \\
        &       & F_2(f,h) &               & \\
F_1(f,qh) & &            & F_3(f,h) & \\
        &       & F_2(f,qh) &               & F_4(f,h)\\
F_1(f,q^2h) & &           & F_3(f,qh) & \\
        &       & F_2(f,q^2h) &               & \\
F_1(f,q^3h)  &           &               & \\
\end{matrix}
	}
\end{prop}
\begin{proof}
	\eal{&I(f)= I_n(f,h) + R_n(f,h) = I_n(f)+c_1h^{p_1}+O(h^{p_2})\\
	&I(f) = F_1(f,h) + c_1h^{p_1}+O(h^{p_2})\;\;(1)\\
	&I(f) =  F_1(f,qh) + c_1(qh)^{p_1}+O(h^{p_2})\;\;(2)\\
	&(1)  \ubrace{\>}{\T{moltiplicando per }q^{p_1}}
	q^{p_1} I(f) = q^{p_1} F_1(f,h) + c_1(qh)^{p_1}+O(h^{p_2})\;\;(1.1)\\
	&(1.1), \;(2)  \ubrace{\>}{\T{sottraendo membro a membro}} 
	I(f)(q^{p_1} -1) = q^{p_1} F_1(f,h) - F_1(f,qh) + O(h^{p_2})
	=\NN
	\ubrace{\=}{q \neq 1}  I(f) = \frac{q^{p_1} F_1(f,h) -
	F_1(f,qh)}{q^{p_1} -1} + O(h^{p_2})
	= F_2(f,h) + o(h^{p_1}) = F_2(f,h) + O(h^{p_2})
	}
	Procedendo per induzione si ha la tesi.
\end{proof}
\begin{exemp}\ilabel{Romberg}
	Integrazione di Romberg.\\
	Sia $C_N(f)$ la formula dei trapezi composita uniforme:
	\eal{&
x_{i}-x_{i-1}=h=\frac{b-a}{N}\;\;\forall i=1,\dots, N\\
&C_{N}(f)= h\pton{\frac{f(a)+f(b)}{2} + \sum_{i=1}^{N-1} f(a+ih)}
}	
Sia $f\in \sczn{\8}{[a,b]}$. La formula di Eulero-MacLaurin afferma che:
\eal{&
I(f) = C_N(f) + c_1h^2 + c_2h^4 +\dots + c_kh^{2k}+ \dots
}
quindi e' possibile applicare l'estrapolazione di Richardson ad $f$
(\vedi{estrapolazrichardson})
\end{exemp}
\begin{prop}Integrazione adattiva.\\
Sia $f\in \sczero{[a,b]}$, $I_n(a,b)$ una formula di quadratura che approssima
$I(f)$ sull'intervallo $a,b$. E sia $I_n'(a,b)$ una approssimazione migliore
di $I_n(a,b)$ (ad esempio ottenuta tramite l'estrapolazione,
\vedi{estrapolazrichardson}).\\
L'integrazione adattiva si puo' descrivere semplicemente dall'algoritmo
stesso:
\def\a{{\alpha}}
\def\b{{\beta}}
\eal{&\oname{IntAdattiva}(\a,\b):\;\;\\
&\qq M=:I_n(\a,\b) \\
&\qq N=:I_n'(\a,\b)\\
&\qq \Se  |M-N| < \frac{\eps}{b-a} (\b-\a)\\
&\qq \qq I=: N\\
&\qq \textbf{Altrimenti}:\\
&\qq \qq \T{Suddividiamo l'intervallo e calcolando ricursivamente l'integrale
composito:}\\
&\qq \qq I=: \oname{IntAdattiva}\pton{\a,\frac{\a+\b}{2}} +
\oname{IntAdattiva}\pton{\frac{\a+\b}{2},\b}\;\;\\
& I=: \oname{IntAdattiva}(a,b)
}
il risultato $I$ e' un approssimazione di $I(f)$ con un errore $<\eps $.\\
(!)Bisogna pero' fare attenzione sulla scelta di $I_n'$ (vedi
dimostrazione)(!)
\end{prop}
\begin{proof}
L'integrazione adattiva al $k$-esimo passo utilizza la seguente formula
composita:
\eal{&C_{2^k} = \sum_{i=1}^{2^k} I_n(x_{i-1},x_i)\\
&\T{con } h=\frac{b-a}{2^k},\;\;x_{i}=a+ih
}
Sia $I^{(i)}=I^{(i)}(f)$ l'integrale esatto di $f$ in $[x_{i-1},x_i]$.\\
(!)Se $I_n'$ e' sufficientemente accurato(!) abbiamo:
\eal{&|I^{(i)}-I_n(x_{i-1},x_i)| \approx 
|I_n'(x_{i-1},x_i)-I_n(x_{i-1},x_i)|  = |M-N| < \frac{\eps}{b-a} (x_{i}-x_{i-1})
}
Quindi
\eal{&|I(f)-C_{2^k} | = |\sum_{i=1}^{2^k} I^{(i)}-I_n(x_{i-1},x_i)|
\le \sum_{i=1}^{2^k} |I^{(i)}-I_n(x_{i-1},x_i)| <\NN
< \sum_{i=1}^{2^k} \frac{\eps}{b-a} 
(x_{i}-x_{i-1})  \ubrace{=}{\T{somma telescopica}}  \frac{\eps}{b-a} (b-a)
=\eps 
}
\end{proof}

\ifpdf
\section{Formulario}
\includepdf[landscape,pages=-]{formulario.pdf}
\fi


%%%%%%%
\printindex

\end{document}