Appunti di Teoria di Calcolo Numerico Andreadd it

Appunti Di Teoria Di Calcolo Numerico Andreadd It-Free PDF

  • Date:17 Oct 2020
  • Views:1
  • Downloads:0
  • Pages:31
  • Size:1.11 MB

Share Pdf : Appunti Di Teoria Di Calcolo Numerico Andreadd It

Download and Preview : Appunti Di Teoria Di Calcolo Numerico Andreadd It


Report CopyRight/DMCA Form For : Appunti Di Teoria Di Calcolo Numerico Andreadd It


Transcription:

Epsilon macchina l errore dovuto al fatto che l insieme ha un numero finito di cifre 16 in. decimale tale che, L epsilon macchina la distanza tra e il suo successivo inoltre all aumentare della. dimensione del numero l diventa sempre pi grande mentre all avvicinarsi a 0 diventa. sempre pi piccolo, Distribuzione floating point l insieme una retta discontinua con distribuzione non. uniforme bens pi densa vicino allo 0 e sempre meno densa man mano che si aumenta con. l ordine di grandezza dei numeri,Numero macchina minimo. Numero macchina massimo, Cardinalit di quantit di elementi numeri nell insieme floating point con lo 0 aggiunto. o dovuto al segno, o dovuto a tutte le possibili cifre della prima cifra della mantissa tolto lo 0.
o dovuto a tutte le possibili cifre delle altre cifre della mantissa. o tiene conto di tutti i valori assunti dall esponente. o serve per includere lo 0 nel conteggio,Propriet di. o Commutativa,o Non unicit dello zero se succede che. o Associativa purch oppure non vada in,overflow Ad es se posto ma allora si. ha un fenomeno di overflow Infatti non dar overflow in quanto non. viene mai superato in risultati intermedi cosa che accade quando facciamo. o Cancellazione numerica fenomeno dovuto all approssimazione causata dalla differenza. tra la base con cui viene immesso un dato decimale e la base utilizzata dalla. macchina binaria Infatti se si calcola con il calcolatore posto si ha. come risultato e non come risulterebbe realmente,Teorema di Abel. Non esiste un numero finito di passi per trovare le radici di un polinomio di grado uguale o. superiore al 5 In pratica non esistono formule chiuse per trovare le radici del polinomio. Schema iterativo metodo per il calcolo diretto delle radici di un polinomio mediante il quale. grazie ad un punto di partenza detto guess iniziale si ripete un numero finito di passi. generando una successione di soluzioni che deve convergere alla soluzione con una certa. velocit e arrestandosi una volta raggiunte alcune prestabilite condizioni. Ordine di convergenza velocit impiegata da uno schema iterativo per raggiungere la. soluzione con la precisione richiesta Maggiore la velocit migliore lo schema utilizzato in. termini economici di tempo, Criterio di arresto condizione con la quale decido se continuare a cercare la soluzione oppure.
se fermarmi in quanto l accuratezza della soluzione appena trovata mi soddisfa. Stimatore elemento con il quale impongo la precisione desiderata per la soluzione Viene. solitamente relazionato all errore il quale viene maggiorato dallo stimatore. Metodo di Bisezione,e almeno un tale che teorema Zeri. Questo metodo diretto serve a trovare una radice di un polinomio purch la soluzione sia. compresa tra e Per farlo si sceglie l intervallo lo si divide a met e si cerca in quale. semi intervallo si trova la radice sfruttando il teorema degli zeri Si ripete questa procedura. volte fino ad avere il semi intervallo esimo minore della tolleranza richiesta sulla soluzione. Il criterio di arresto con tolleranza L intervallo esimo poich. quello iniziale e ad ogni iterata viene dimezzato Il numero di iterazioni minimo al fine di. raggiungere la tolleranza richiesta si trova nella seguente maniera. Essendo un numero non intero se si esegue l algoritmo di bisezione un numero di volte pari. all intero successivo a si sicuri di avere la precisione richiesta Se il metodo stato. eseguito correttamente si avr che, Criterio del residuo criterio d arresto che si basa sul residuo Il residuo il valore della funzione. nella posizione ovvero Quando il valore assoluto di questa quantit. minore della tolleranza allora si pu arrestare il metodo diretto per trovare Tuttavia se la. derivata della funzione in molto maggiore di 1 si pu avere una sovrastima mentre se la. derivata in molto minore si pu avere una sottostima Lo stimatore che sfrutta il residuo. buono quando la derivata in circa 1, Criterio dell incremento criterio d arresto che si basa sull incremento L incremento la. differenza tra due iterate successive Se questa differenza minore della tolleranza si pu dire. di essere abbastanza vicini alla soluzione,Metodo di Newton. Questo metodo diretto per trovare le radici di una funzione sfrutta delle rette tangenti alla. funzione passanti per le varie, Newton approssima Taylor infatti la formula dell iterata successiva si ricava da Taylor.
troncata al 2 ordine, Se trascuriamo l O grande del secondo ordine si ha che per sufficientemente grande. abbiamo come iterata finale e quindi,dalla quale si ricava l espressione di. Convergenza del Metodo di Newton, Condizioni per la convergenza del metodo di Newton. 1 deve essere sufficientemente vicino ad cosa che si pu fare facendo qualche. iterata con bisezione oppure guardando il grafico della funzione. 2 deve essere una radice semplice ovvero, Se sono soddisfatte queste condizioni Newton converge Con che velocit. 3 Se allora si pu dire che l ordine di convergenza dato dal limite. Se il limite verificato Newton converge quadraticamente. 4 Se multipla allora se Newton converge lo fa linearmente. Ordine di convergenza, Uno schema iterativo ha convergenza se indipendente da tale che.
Se il metodo converge linearmente mentre se il metodo converge. quadraticamente e cosi via per valori maggiori Essendo si ha che per. necessario che per avere convergenza altrimenti l errore non diminuisce ma. aumenta ad ogni iterata,Metodo di Newton modificato. Il metodo di Newton modificato serve nel caso si abbia una radice multipla ad esempio. ha radice multipla in e Se si ha radice multipla e se. questa radice ha molteplicit allora lo schema diventa. il quale converge pi velocemente del metodo standard di Newton. esiste anche un ulteriore metodo chiamato Newton Adattativo che cambia ad ogni iterata. Punto fisso punto fisso se, Trovare il punto fisso di una funzione equivale a trovare l intersezione della funzione con. la bisettrice del primo e del terzo quadrante Si possono avere pi punti fissi un solo. punto fisso o nessun punto fisso,Metodo di Punto Fisso. Il metodo di punto fisso serve per trovare un punto tale che sfruttando una. funzione tale per cui Esistono pi adatte allo scopo ad esempio. L iterazione di punto fisso si basa su,Il metodo di Newton un metodo di punto fisso con. Tipologie di convergenze a punto fisso, detto attrattore se si ha convergenza repulsore se si ha divergenza.
1 Convergenza non monotona es e decrescente,2 Convergenza monotona es e decrescente. 3 Divergenza non monotona es e crescente,4 Divergenza monotona es e decrescente. Per monotona si intende oppure a seconda, del caso mentre per non monotona si intende che le varie iterate sono maggiori o minori. ad a seconda dell iterata ma ecc,Teorema Globale per la convergenza di Punto fisso. 1 Condizione sufficiente per l esistenza di, 2 Condizione sufficiente per l esistenza di e per la convergenza di punto fisso.
richiesta lipschitziana, Dimostrazione teorema globale per la convergenza di punto fisso. 1 Prendiamo, Ci vuol dire che per il teorema degli zeri almeno un. 2 Supponiamo per assurdo che,entrambe punti fissi,Si ha quindi che per assurdo perch lipschitzianit. Si conclude dunque che, Per dimostrare la convergenza si considera l errore. per punto fisso metodo e definizione,Per lipschitzianit da cui.
Di conseguenza,Posto l errore si ha quindi che,dove conosciuto e limitato mentre. tende a 0 per in quanto e perci punto fisso converge. Teorema locale di Ostrowski,Dimostrazione del teorema di Ostrowski. un punto compreso tra e per il teorema del valor medio. Per ipotesi di continuit allora vale anche che sostituendo diventa. Fattore asintotico di convergenza indica la velocit con la quale si raggiunge La. velocit di convergenza della successione di iterate aumenta man mano che. Con la successione diverge con non posso dire nulla sulla convergenza. mentre con la successione converge come visto con Ostrowski Nel teorema. globale il fattore asintotico, Generalizzazione di Ostrowski per convergenza quadratica. Dimostrazione di Ostrowski per convergenza quadratica. un punto compreso tra e,Essendo per ipotesi si ha dunque. Per ipotesi di continuit allora vale anche che diventa. Generalizzazione di Ostrowski per ordine di convergenza 2. Dimostrazione di Ostrowski per ordine di convergenza 2. un punto compreso tra e,Essendo per ipotesi si ha dunque.
Per ipotesi di continuit allora vale anche che diventa. Per trovare basta cercare la prima derivata che non si annulla in quanto l ordine di quella. derivata l ordine di convergenza, Dimostrazione del fattore di convergenza di Newton. Newton converge con quindi,Valutando in e ricordando che si ottiene che. in Newton per con molteplicit si ha e, Legame tra errore e criterio d arresto dell incremento. l incremento,per la definizione di punto fisso,Se allora compreso tra e. Da qui si nota che il caso ideale In questo caso l incremento. diventa un buon stimatore dell errore in quanto si ha Se perdo. affidabilit nel criterio basato sull incremento per radici semplici il che rende. questo criterio d arresto favorito in questi casi, Andamento errore stimatore per radici con molteplicit diversa da 1.
In Newton standard se ho con molteplicit si ha e, Questo comporta ad avere all aumentare di e quindi a perdere affidabilit nel. criterio d arresto dell incremento L andamento dell errore e dello stimatore incremento. sempre parallelo per ogni ma la velocit di convergenza diminuisce all aumentare di. mentre aumenta la distanza tra errore e stimatore, Estensione di Newton a sistemi di equazioni non lineari. Dato un sistema di equazioni non lineari,Cercare le radici significa cercare dove ogni. Tuttavia il metodo di Newton prevede una divisione cosa non possibile tra vettori per questo. motivo si utilizza la Jacobiana dove indice equazione e indice incognita. Newton cosi diventa,Regola di Cramer per sistemi lineari. Dato il sistema lineare con soluzione con la esima soluzione. con matrice ottenuta sostituendo la esima colonna di con. Il problema di questo metodo che se sfrutta la regola di Laplace per il calcolo del. determinante ha un costo computazionale elevatissimo circa. Metodi di risoluzione,1 Diretti numero finito di passi.
2 Iterativi numero infinito di passi,Metodo della Fattorizzazione LU. Questo metodo per la risoluzione di sistemi lineari crea due matrici triangolari e a partire. da tali per cui,una matrice triangolare inferiore lower. una matrice triangolare superiore upper,Inoltre essendo il prodotto di due matrici se il. significa che non ci sono elementi nulli sulle diagonali di e di e non ci sono autovalori nulli. per le propriet del determinante, Il metodo consiste nel trovare e e risolvere il sistema con alcune sostituzioni. e ponendo risolvere prima e poi Essendo e, triangolari i due sistemi possono essere risolti con i due metodi seguenti.
Metodo delle sostituzioni in avanti, Si utilizza per risolvere un sistema dove conosciuta e triangolare inferiore mentre. vettore colonna di termini noti L elemento esimo della soluzione si trova con la formula. Costo computazionale della risoluzione con ordine della matrice. Metodo delle sostituzioni all indietro, Si utilizza per risolvere un sistema dove conosciuta e triangolare superiore mentre. vettore colonna di termini conosciuti L elemento esimo della soluzione si trova con. Costo computazionale della risoluzione con ordine della matrice U. Fattorizzazione LU, Per trovare le matrici e bisognerebbe risolvere il sistema di equazioni con. dimensione della matrice con incognite le componenti di e che risulterebbe. sottodeterminato A fronte di ci si deciso di porre uguale a ogni elemento della diagonale. della matrice Si calcolano i moltiplicatori che verranno posti sulla riga e sulla colonna. della matrice facendo scorrere Il numero in apice tra parentesi indica la. fase della fattorizzazione oltre ad indicare la riga base di partenza in quanto la matrice una. volta svolta la fattorizzazione diventer quindi Partendo da. Calcolati gli si procede mettendo in posizione, In questo modo si annullano tutti gli elementi della prima colonna sotto la diagonale di. A questo punto si incrementa e si ripete il procedimento del calcolo degli e degli. Alla fine del processo che viene eseguito per si ottiene una matrice. triangolare superiore che altri non che la matrice. Il costo computazionale della fattorizzazione,Metodo di eliminazione di Gauss MEG.
1 Metodo LU si scompone si risolve con e poi si risolve. al fine di ottenere la soluzione di Questa strada si sceglie se si deve risolvere. un sistema del tipo in quanto eseguo una volta sola la fattorizzazione. Ha un costo computazionale di, 2 A orlata b e sostituzione all indietro si orla con e si fattorizza la matrice ottenuta. risolvendo poi con il metodo delle sostituzioni all indietro Ha un costo computazionale. Il MEG viene utilizzato per il calcolo dell inversa risolvendo sistemi che hanno per termine. noto le colonne della matrice identit e le cui soluzioni sono le colonne della matrice inversa. Condizione necessaria e sufficiente per fattorizzazione LU. Affinch la fattorizzazione LU di una matrice esista e sia unica necessario e. sufficiente che le sottomatrici principali di con siano non singolari Le. sottomatrici principali sono matrici ottenute eliminando dalla matrice iniziale lo stesso numero. Appunti di Teoria di Calcolo Numerico Schema iterativo metodo per il calcolo diretto delle radici di un polinomio mediante il quale grazie ad un punto di partenza detto guess iniziale si ripete un numero finito di passi generando una successione di soluzioni che deve convergere alla soluzione con una certa velocit e arrestandosi una volta raggiunte alcune prestabilite condizioni

Related Books