Energy Engineering - Metodi Analitici e Numerici per l'Ingegneria

Appunti Parte Numerica

Divided by topic

SCHEMA MANI PARTE NUMERICA 1) TEORIADELL'APPROSSIMAZIONE E DELL'ARITMETICAFINITA Te o r i adell'approssimazioneConsidersPFinproblemafisicodevisolvere e suppongoesiste uno soluzioneIt -> Vo g l i ocostruirein modellematematicoPMpersemplificareilproblema fisice me dicui supplemel'impossibilitàditenercontoditutti:dettaglidelPF -> Spesso _ peró _ : problemimatematic nonpossoessere risoltianditicamente.deve,pecióaffidarmied i problemsnumericocheapprossimiPMAPN evrovediervore Possosintetizzareilprocesso come: PFmodells7 PMnumer:co> PNSiquantificanoduetipidi errore: Tr-T - n · erroredimodello: en=11Tr-TIl introdettedeltrascurarealcuni espettirea · errorenumerico: en-11T-Tullche misureladifferenzetwosoluzioneesattadelmodello elosoluzionenumerica-> Puòancheessere considerate comeerroreditrancamentedellimplementazionesulcalcolatore consistenza e convergenzadi un metodo numericoConsidero un problemsmatematico con incognite x daid e velezioneF -> Ingenerevisolvo:F(xd = 0 Risolvendonumericamenteallengeuna formeapprossimatedelprobleme:Falkenda) = a-> Ilparametro nindicei numerodiintervalli otimestepIngeneratevoglioche x = x-Hobisognoche:dareaIn sie consistenteConsistenza: un metodo numericoèconsistenteseesolo se h Fukurdal=erossiselosoluzioneesattoé anchesoluzimedeproblemanumericapern -+ro Forteconsistenza: se Fax.) = 0 FnConvergenza:Unmetodonumerico Fukundul = eè convergente see solose: FaceIno=nord) taleper cui Fn>n() = > 1x - xnll = 2-> Possosempretrevove unnoeunasogliepercuiIIX-xall sixpiccole a placare Aritmeticafloatingpoint Implementando uno schemenumericoinun computerdotbiomeopprossime ve deinumeriEIRche non possonoessere rapprentatipachéhannoinfinitecifredecimali -> Devorappresentare i nume:CIR in evitmeticoflootingpantSuppongocheesiste une funzioneflchedato unnumeroe inentrato - restituisce unnumero fl)rappresentabiledalcalcolatore e opportenenteall'insiemeIFcIR -. Un numero yelt édetrite come: y = (-1)(De..et) ca:S = segno/se s = 0 yc.se s = 1 y =a B = bese,adesempio20102 = érespientedellabase08....ert= mantisse assie:numeri cheseguendlevirgoletaiper cuiref e &EC-1sinscenceIFrisultadefiniteda put numerodicifresignificative edarmassimoeminimaesponete(U-L) -> IF = IF/Bt __ U) -> LocupozionedimemoriedipendedellelunghezzadimontissatedalrangediesponenticonsideratoEsempio: numer: floating point in doppieprecisionehanno64bitcoscune: . Ibitpe:segne · 11bitperl'esponete = loga/U-L+2) Ivoviedo-102201023) · Hlogz/)= 53perlomantisseitnumerodicifre),di cui32memorizzat -- 16cifre inbase10 -> F/2.52.-1022.1023) - Il numerepiù granderappresentabile e B = 1 2)EQUAZIONI NONLINEARIMetodi numeri per equazionvalineariconsiderando we funzionescalarecontinue f.ilproblemschevogliamevisolvereé:f(x) = 0averetrovareglizerieleradio a difIngeneraleè difficiletrovaregliaenditicamenteintroducequindi unoscheme numericochefornisca uebuoneapprossimazione -> Definisca un algoritmoiterative:parto da un vore x ditentative ↓.aeottengox do xottengo 2Xecosì via.Costruisce una sequenzaaffinchéperK-1 0.X -a-> Ilmetodo si diceconvergentese lim x = ax - Metododibisezione Te o r e m adeglizeri:data una funzionef.arb]-sIRcontinue su feb. Se fralf(t) =e alloraesistealmeno una talepercui f(a) = e Sapendo ciò posso creareun algoritmodibisezionechegenereadognitevozione in intervallopiù piccole incui tocondizionefralf(b) = 0sisoddisfatte. -> Inveceditrovare a folgoritmo cercaun intervallotaleper cui Iff)l = tellPseudo - codice:BisezioneCapiamo seè perchéilmetodoconvergeameno: =* = (26) ↓ 114 = 16 - c4) = 21144 = ... = Eulb - cDefiniscaquindierroree come: le4 = (x - alperò noncrescoa-> Possodirecheallepeggioerrorerare come lintervallochestoconsiderando le Igelbel PerK- t o l e k ) --- ILMETODOCONVERCE1x4) - a Struttolorelazioneopponetrovatepertrovarenumerodiiterazionnecessarieadattenereunerroreminore diuna tollerenzeEprefissate le lb-el = - * e --- k - 1 = legale) -- : loga() -1 "¥ > loge/) - ecankarrotondatoall'intereLaanvergenze noné monotonamentedecrescentesuperiore Te o r e m a e :Se una funzionehamolteplicitéalgebrica disparialloreesistemintornodi a taleper cui leipotesidelterremadeglizerisono verificate.Molteplicità1: f(e) = e _ f(a) =e Molteplicità3:f(a) = e-f(d) = 0-f"(r) = ef"(a) =e desistenza noné assicurate seviè molteplicitéalgebrice pariL' a l g o r i t m opuòessereancheutilizzatoperdeterminere una talepercui f(a) = g(n) -> Riscriveilproblemacercandoglizeridiunafunzionehittaepercui: h(x) = f(x) - g(x) - h(n) = f() - g(n) = 0 Metododipuntefisse Riscrive ilproblemadella ricercadeglizeriinquestoforme: x = f(x)Esempio:f(x) = x - cesXCercovef(x) = 0ècomecercarex-cosk = o*=cosx = g(x) - Cercoilpuntofisse6. G(x) = cesxSe =(B) = cos ellover fl) = B = e ChiomeGry)funzionediiterazione e costruisce unasequenzadisoluzio inquestomodo e partireda un gressinizialeXo:Pseudo-codice:x = f(x) PerK =oimpostox = X.fork = 0.12.... Questemetodo um ésemprecavergente: xx +1= f(x) x = x + 1 end Te o r e m a3:Siconsiderilasequenzex = f(x) canto Suppongoche:1)4:(e,b]--(ab)26 = ct/12b]) 3) 16(x)) = 1 xc (zb]Allowsthe mnicepuntofisse a c/ab) e [x23convergeeda perognisceltodixc(.6]Inoltrerare: mette dal Quindi ilmetodoconvergeselafunzionehaderivateminoredi 1 inun intervallocontenentelasoluzione a. Ilteoremegaventisceleconvergenteglobale in lab] non sempredeterminabile a prioriTe o r e m adiOstrowski Si aun puntofissodellefunzioneecontinue e derivabileinuninternodia-> SeI(a)) = 1allows7dataledalesequenze (x) convergeoda perogni* treche:Ix: - al=d MetododiNewton Metodoalternativoperlaricercadeglizeri-Datalafunzione fel. Inrettatangente arf inx è pari a:v(x) - f(x) = f(x) - r(x) = f(x) + f(x4)(x - x4) x - xkDetoxx *** étrovatointersecandolarettatangente a fin x conlessex -> vx4) = f(x4) + f(x4/xk - x4) = 0 - x42 = xk - f(x)f(x) I metodo è sololocamenteconvergente e AlgoritmodiNewtolascelteinizialediXhaimpertesulfunzionamenteDato X. fork = 012de dell'algoritmo xk +2=x 4 - f)f(x)x = x + 1era Te o r e m a5:Sief.10.6]-R ue funzionediclasseC in (0.6)Sie a talechef(a) = ef(n) =0-> Alloraesistey so talechescegliendox can Ix-aly. allorosiha:VKEIN|x-r = 4 -> Inoltre ilmetodorisultaconvergente:lim x = aK- -Infine ilmetodohaconvergentequadratica:I'm*** - 0 = c = f"(a) x - (xk - a)2f(a)Te o r e m a 6:Siefec/feb)) exosufficientemente vicinooaesiacon molteplicité, 1 -> IlmetododiNewtonconvergesololineamente:lim(** - 21 = 2cmexc = 1x = 0 (x - a) METODO DINEWTONMODIFICATOIntroduce in definito come molteplicitàalgebricadelo zeroa - Modificaquindi algoritmo come segue: Datoxwhilecriteriodiconvergenza)do-> Seilmetodoconvergealloreconverge-a =x 4 - mf(x)quadraticamente(semprelocamentelf(x)k = x + 1 en CRITERIDIARRESTOSuppongodiavere un algoritmochegenere unesequenze [x tarepercuilim x=ak - + Problema: come fermolelgoritmo in modocheper i datox sie sufficientementevicinoada? "¥ a primaideséquellediarrestarefolgoritmoquandodate una tolleranzeE: le4=1x-a) = E - Richiedeperòla conoscenza di e-> Devoutilizzare uno stimatoredell'erroreche mi garantisco chel'errore siminoreo ugualeallostimatorescelteStimatore1: (x *** - x4 = E Stimetove 2. * = f(x) -> Arrestotelogoritmoquando Ic* = E -> Affidabilequando fialealtrimentiicriterepuòesseretropposeveroperIffalk 1oviceversa perl'allo SISTEMIDIED.NONLINEARI Dueconsidereilproblemadiricercardizericonunsistemadi n equazionnonlineari:f = (f...f]a = (a..a)!x = (x..x]/fexe ....(n) = 0 Informacompate "- (a) = 1 (fute....(n) = a Inquestocasonon possoutilizzarelabisezionemultivariabile -> Utilizzoil metododiNewtonnel caso vettoriale:x + 2 = xk - f(xk) -> Definiscolincremente come: (x = x *** - xk =- f(x4)f(x)f(x)&Hengo: fk)(x =- f(x) - UTILIZZABIEVETTORIALMENTEInformavettorialediventa: (5x](14)(x =- f(x) "¥ Matricejacobionedif>x = 1 + -xk ·1) = E e Nata Persiste e > Jx/x45xk =- f(x4)-2x =- (jx(x4)5f(x) det(3x()) = 0 -> Newtonpersistemi averge quadraticamentese # convergenzalocaleJefal é invertibile 3) METODI DIRETTIPERSISEMILINEARI Possoesprimere:sistemidiequazioninformematriciale:x1 + x2 + x3 = 12x+3x2 + 3x3 = 2 -> -E(2)Ax = 1 7x1 + 8x2 + 9x3 = 3 re CercoXEIR"cherisolveilsistemedi n equezioinn incognite:Ax = bcmAck* Te o r e m a7:IlsistemaA1=1 ammetteunoeuna solasoluzioneseuno delleseguenticondizionequivalentiè verificato:1) Aéinvertibileesistequind:A tale che: AA* A A = I2)Ilvangodellematriceen3) IlsistemeomogeneoAl = eammette1 = 1comemicasoluzioneNetAiPossoancherisolvereutilizzandolequazionediCromer:Xi=detAincui Anélamatriceattenutosostituendo l esterinesime colonneNonutilizzabile:IlmetododiGramerichiede unnumero di flop nellordinedei109141Iostessovaleperun'operazione comeilcercoo ~ dellamatriceinverso AClassificazionemetodinumeric ->Metodidivetti(CremereliminazioneGauss...)-Tro v a n olosoluzione conunnumere note e prioridi passi -> Metodiiterativi(JacebirGauss-Seldell -> Genere una sequenza [x] taepercui:limx = IK-> FATTORIZZAZIONELU · Date una matrice AEIR*"supponiamocheesistendiematricL.VeI**tolipercui Létrangere inferiore e Uétriangolovesuperiore->glielementi bis = 0per jai-Decompongo Anelsequentemodo:A = LtVij =0 perjxi · Perilteorema7:sistemeérisolubilese detA)=0meperilteoremadiBinet: 8 = det/A) = det(LU) = det()det(U)dett) = hal --- DunMaessendoLeUtriangolarialloredet(U) = verUe ... Un-> E necessariechebis eWii=0Xi = 1....Perchéèutilequestafattorizzazione? -> Possoscrivereilsistemo come: Ax = 1-Lux = 6 -> (y = 1 -14 = 1 -> Risolveilprimosistemaconun elgertiedisostituzione in [Ux = 3avant: /lege = be ! by = 1 - ber (32)02] - enystery e I Ilneget ... + langn = buDallaprimaequazioneviceve yechesostituiscenelleseconda opereda cuivicove be a cosivie fino a guAlgorithme:ye = - y = -zeigi) peri = 2...Unavoltetrovato possorisolvereendogamenteilsisteme UI=I partendoperòdall'ultimarigaAlgoritmo: Xn = xi=/y-kisti) peri = ne.....I generico passorichiede: i - 1prodotti lisys i-esomme i sottrazionee bi j = 1 1divisione -> Ilpossorichiede2i-operatoevendonoti agli altrivaloriCostoglobe = (i-s) = 2-s = 2 - n = e -n =Aterens un risultateanalogoperlasostituzioneall'indietrodellamatriceU -> Lerisoluzionedelsistentlineare (s dateLeUhecostocomputazionalepari a 2n DeterminazionematriciLeUConsidero AIR**: 31 = V11Un212 = U12 s ↑82 = Reeves I pal: essere -es". 22= lez Une + Rezunz -> fissandolin=1Ki alenge nequazioniin nincognite METODO DIELIMINAZIONEDIGAUSS -> UsatopercostruirelematriciLeOEsempioStrategia:cercovediottenere (E)(E) = (2) - concombinazionlinearidelle - Pange e righe. un sistematriangolareCalcoloAsottraendolaprimarigemoltiplicatoper tale secondereanerogementeperlaterze -> Applicolostesseoperazioneperilrettoret↑ =E(E)=) - PossosedereM2twepercui ME) Sottruendoinfinelaseconderigemoltiplicateper e allaterzevigeattengoeoperandoallostessomodoAlgoritmo: I 8)) Dato * = AforK=1.....do:for i = k + 1....do: -> Posso usareuna sequentadimatriciain" - MoltiplicatoreA= A.A"....." = 0 fr = erniForj = k + 1 ..... ndo: -> CosicrealamatriceU. neusende 2ijei-Siner i multiplicatoriliteposso creareancheLcome:entres bi-linbu; - e:e] endend I) coste dellecreazione dellematricicomputazioneésull'ordinedei n -> Moltopiùvelocerispetto a CrameSelamatriceAesparseil numerodielements nonnulliemoltoinferiorerispettealedimensionedellematrice) sipuò generare ilfenomenodelfill-indaverdepieceecostoselematriciLeUE sistenzafattorizzazione(UIlcriteriodimatrice nonsingolare, essicondeterminantenonnullo nondesteegerentineresistenzadellematriciLeU -> DefiniscelesottometriciprincipalidiAcomelematriciAnattenteestraendoleprimeirighe ei colonne.An = fax)Az = (e)... Te o r e m a8But una matrice AeI*" non singolare.Io sua fattorizzazimeLUesiste see solo se lesottometriaprincipaliAsditdiordinei = 1....nesmonon singolari -> Ilteoremafornisce ma condizione necessarioe sufficiente, me esistoneanchecondiziosufficienti:1) SeAéma matrice a dominanzediegendestretteperrighe e colonne&SS18:perrighe: Kinkjetig i = e.....npercolonne: lajjkleij) j = 1.....nj = 1.j =i 2)SoAéuna matricesimmetricadefinitepositive, ossier: - coji = bisKij = 1....n(simmetrio) - di = autorder:d:A o oppure AX(0x ex A1 = 01 = e Te c n i c adelpivoting:permutareopportunamentelerighedellematricedipartenzeperevitoreelementipivotalinulli - I ↑113 I -> L'o p e ra z i o n e è descrittodauna re 20 - 4 - > 035matriceformatoda1e& - h tre percui:PA = LUPA x = P6 EliminazionediGauss can pivoting -> LokolateLPeU _ tsolamedivento:PA = LU Ax = 6 - PA x = P6-Lux = P6 &V/y = P6Costocomputazimale I = = 3CalceleLUP = In Sostituzione = 2n2Calatecnicedelpirotingpossoottenereune -fatorizzazione (VperogniAinvertibileStabilitàmetododieliminazionediGaussStabilità - DipendenzedellasoluzimedallaperturbarzonedeidatidelproblemaPersistemilineari - provea risolvere un problema distrutto/A + dA)(x + dx) = 6 + 66Ipotesi:SA = 0II = cmd(A) Il fallterrore commesse soddisfaquestadisugraglianza:IEllIl6Il/max(A) -> Incuicand(A) =-> cmdA)=1soAébencondizimento I min(A)In caso contrario,dopiacelierroridi1risultanograndierroridiA ALTRIMETODIDIRETT-Fatorizzazionedi Cholesky:A-RTR ca Rmatricetriangolaresup.Costocomputazione: Int ·AlgoritmodiThemes:and caseincui A six tridiagonale, ossiase eg =0 per In-jk 1-Fattorizzazione(U-> CM Bit s canai= bi-i is->21 = 01 4)METODIITERATIVIPERSIS.LINEARI Date no matriceAtR* em vettore 1el" -> Cerco elR" taepercui: Ax = b - Unmetodoterativedaunsequenze [4] checonvergeallesoluzimeparKusaMetodoiterativoconvergenteDatoin rettoreiniziereinmetodoiterative si diceconvergentese: !** = m = e canet = x - x*é l'errore commesse alpassoKFormageneratedimetodoiterative:** = Bx+1 cm Belmatrice diiterazione yEIR" costruitodeAet -> Begpresi in modocheilmetodo siconsistenteMetodoiterativoconsistenteUnmetododelleformea Bag éconsistente se Beg sonotaicheE = Bx + g -> Ilmetodo si fermasullasetesatteTe o r e m a9:ognimetodoconsistentesoddisfa alBeekt = 1 - 1=B1 + g - Bx - g = B(x - xk) = Be - Raggiospettatedimatrice: (B) = n1XiBS -> Essosoddisfalaproprieté:limB = 0)p(B) = 1 - Inoltre:p(B) = lBI K -ro Te o r e m a10:condizione necessariae sufficientediconvergenteUnmetodoiterative in forme =Bat é convergente i Suppongoche (B), ossia esistealmenoun tre perau: III -> Scelgo x taeper cui e = x-x=autorettoreassociatoer -- Bei = deSavivoVe roveepassoKcome el = Bek _ Bree _ ....Be = NeeMexpecieverrore naconvergeperK ->n Considersover A e PEIR** taiper cui: A = P-IP-A) ca P = precondametore -> Derive Be: As = 6 -> B = B (p - A) -> (P - (P - A))x = 6 -> Px = (P - A)= + 1 -> g = p -> x = p - 2/p - A)x + P26-Residuodelprobleme: I6 - Ax- nulloper salesate -> xk + 2 = p-/P - A)x + p - 26 PI* = P-A)16--PROBLEMALINEAREDARISOLVEREADDONPA S S OKPax + 2 = Pxk - Ax + 6Px + 2 = P=4 + rkqx + 2 = x + PkMETODODIJACBBI Definisco, come matriceP.lamotricediagonaleDchehaperdiegonerelestesser digenzediAP = D = dieg(A)) -> Loscrivecome. DARD-ATAP - xDID-AIA + D1 cm 5 _ (8....e) eseDetwisco:Bs = 5D - A) = F - BA = " I - ser- x= E I g = B 26 · lusoluzione x eindipendentedateartecomponenti - Llgoritmo è parzializzabilee · Ilmetodoconvergese p/Bj) = 1perciópiùveloce METODO DIGAUSS-SEIDEL ScompagetomatriceA in A = D-E-F con: e -i]roënb....] E= I -In---Ennes I PangoD-Ecomematricediprecondizimamento--P(*** = (P - A)2 + 6(D - E)14 + 1 = Fxk + 6 -- Formacomponentepercomponente: XR = ibi-ese) Questovoltoper conoscere adevogia amoscere gi X perj = 1....i = 1-> Menoparzializzabile ma piùveloce e convergere MatricediiterazioneBas=(D-E)-* (Metodoconvergentesep(Bos) = 1)Altrecondizionisufficientidiconvergenza: · A é o dominanzedegenerestretteperrighe o comme · A é simmetrica e definitapositive METODODIRICHARDSON ConsideroA = P-/P-A) edesprimelagenericoiterazime come. P1* = (P - A)X4 + 6 = PX - Ax + 1 = PX + 1 - 2* = x + Pr T -> Generalizes conunvalore a costante:xk + 2 = xk + a - 2,x /MetododiRichardson)stazionario -> Generalizzo conunvaloreevariabile* =x am- Metodo charde adognipasso K. Matricediiterazione: B = I - am*A Te o r e m a11Suppongoche si nonsingolaree PA siadefinitepositiva(deco -> ordinegliautoratori nel seguentemodo: Xes...Inso -> Ilmetododi Richardsonconvergesee soseOxax s -> Esiste un cet= in talepercui il vorggiespettatedellematricediiterazioneB sieminimede - An >Popt = de + AnDimostrazione:DatoBpossoesprimere: suoi autorder: come: 1/Ba) = eabi -> Ilmetodoconverge se (i/Ball = 1 Vize..n11 - axil = 1 - axi - 1 = 1prendoilcaso peggioreadere -oxa = Es -> Ve r i f i c eopt Sapendoche XeBr) = 1-abi eche P(Br) = max. iBall -> OsservoIdi/Bell ervariaredi a /Xe(Ba)lI raggio spettrale,essendoilmassime /Ballautore per ogni è rappresentato/Xe/Balldata curvoevidentiate in giallo InBall -> ataledeoverraggiespettraleminimerisulta aoptdatodallintersezione: e t 1 - adn = ax - 1 - xa(be + bn) = 2"xn Th 2&opt = x1 + n METODODELGRADIENTEConsideroAcR* simmetrica e definitopositive,vogliovisovere Ax=1 -> Atésimmetrica e definitopositive. XAl=4 Aw = dw - ATA w = A -> Xw = AwCostruiscolafunzione F.R- IRquadratica: f(y) = 216 - Ag) + A - (1 - Ay)-La ricercadelpuntominimo difequivaleallesoluzionedelsistemalineovef(y) = 26 - Ag - 26 - Ay) = 2yy - 2 - y + 6 = Gy Calcolodelminimo:0 = Vf(y) = Ay - 11 = 1solvime sis. lineare-Ilmetododelgradientecostruisce unosequenzedeconvergeeminimodifConsidero una formaleggermentediversedichehostessopuntodiminimonelleescissemo diverseminimo: fly) = yAy-yt · Ilmetodofapartedei metodididiscesecaratterizzatide1)direzionedidiscese a 2)possoancanaviovare) x = x + mac im f(x) =f(m) -> Dato e possocredereachiedendoche conquestoposso f siminimo lungo/d) -> dx = 164Ad Perquantoriguarder a unascelteattimaleélamassimediscesedal punto -> 64 =- Xf(x4) =- /Ax - b) = b - Ax = E/METODO DELCRDIENTE)Nuovoresidue: ** = 6 - AXk+=6 - Ara + anc) = -maA-- Gscaedate Algoritmo.Te o r e m a12:ConvergenzadelmetododelgerdienteSe Ac* è simmetrica edefinitepositive,alleveilmetododelgradienteconvergeallesoluzioneAx=6Fx.Inoltrevaleleseguentestimedi X-X*:Ilekl=Clella con= e ifatorediabbatimental con cadAl- -> PachéC = 1allers hmllel = o Inoltre(=cost ->é piccolopercad/A)Matricebencondizimate ->é grandepercadrA)1MatricemalcondizimatMeglio è condizionateApiùvelocementeconvergeilmetodo METODODELGRADIENECONIUGATOGeneraledireziondapartendedegradientedellefunzione -> Combinazionelineave ->x=x4 and = x andep-...- xtese" delle ledirezionididiscesaQuestometodogarantiscechelediversedidiscese sia lineamenteindipendentitwolovepoiché essesono A-ortogmarieA-coniugateDuevettore sa tortogni e Te o r e m a13:convergenzemetodogradienteargentoAlgoritmoSixA = IR* e metricesimmetrico e definitopositivo,allorailmetododelgradconiugatoconvergeallesoluzionedelsistemeAs=VIE IR"inerpiùiiterazion -> Inoltrerarela stima:le = etere della canc = cond(A) - 1(mN(A) + 1 Entrant meteo possono essere-mistorato me matriceinvertibileese -> Ilproblemadiventa PA x = D26 Criteridiarresto.Il " = (cadAl nontroppodeveral2) 11x4 - xk + 21) x E11611 3)INTERPOLAZIONE PROBLEMA:Tr o v a r e ,datounsetdi punti(igil _ ma funzioneinterpolanteossiepassantepertutti:puntidati oinalternativechepassisufficientementevicinoa talipuntiINTERPOLAZIONEPOLINOMIALE Datent1coppiedipunti(igildistinte cercaun polinomiodi gradon Tinel"chepossipergliitspunti -Hn/ki) = yiper i = e....nTe o r e m aInBatnispunti (iyi),can i = e..ntaleper cui Xiexperista esiste moemsolopolinomioineIP"tereche: Tn ( x i ) = yii = 0....nDimostrazione · Costruisce un polinomiodi goden come combinazionelinearedimonom ApuzIP".pax) = en+lext...texsimposizionediposseggioperglintepunti genera un sistemedineeq.lineariinn + 1incognite essii coerficientie· Approccioalternative:costruire mebaseper i polinomi -> Definisceperognii = 0...un polinomiohidi grade ncan leseguenticaratteristiche: X - x,POLINOMCARATTERISTICLixal = 18-Li-ex-x, AlLAGRANGE Questi polinoni sonolinormateindipendentiinfert: elix = ex = xj, Edili;) = 2;Ljk = d = 0j = e..n -> Costituisconoquindi unabasediIP" -> Ogni polinomio puòessere scrito come: Apnel":paxl = b.Loft...+beda) · Aquestopuntocostruiscel'interpolatepolinoniereinteltrecheTu k i l -gi -> T/x) = Egeti) Tin EIP"Tr / X i ) = yeDimostrolaicitàperassurdo:suppongocheEnelp"taipercriminiil-y:-Definisce un polinomiopurin-inchesoddisfa:1) que 2)pn/xil = Tn ( i ) - Finki) = e Però seun polinomiodi grado nsiannullainnitpuntiessedevenecessariamenteessereilpolinomioidenticamentenulla: parlo Ex -> Va d o in contraddizione canlipotesi per cui PueIP" -> Esistesolo un polinomiointerpolate Esempio: 1+1 = 2 -> Cerco un interpolantedi grado1 - Tink)=get() =yetok) + yelek x - x1X - Xecon Lo(x) =- e(n(x) =- Xn - x1Xe - Xe Esempio: n+1 = 3: Analogamente - Tinkl=y-lik Lok) = -4 = e- Te o r e m a15 - Stimadell'erroreDate unintervallolimitato I. siconsideranoinodidi interpolazionedistintiSete(I) alloraxe esisteunataleche:Enf(x) = f(x) - πn(x) = f(2)π(x - xi)(n + 1)! =e Osservache:Enf(x) = swei puntidiinterpolazioneIngenerarenonsihaconvergenza: ((Enf(x))) = e Stabilitàdellinterpolazione:ConsiderosuI entenodiXi -> Interpelzimelagrange:Inf() = f(x)Lik) = geki operatore":interpolazioneConsideroèottenuto perturbandofuE/x = riti Sefufépiccolealloraloé anche Tu f - a f? 11Tuf-Elle = maf- El = fx-fre =>mex Ifkal-fixall white) termine nondipendentedeF. mersolodeivalori i=0....N "¥ . deinod:-COSTANTEDILEBESGUEpermodiequispaziatilacostantevere. An = m hikel-e 6 = 057 + 21 e.n.loghts)Nod:Chebycheu-Gruss-Lobeto-nod: conunaspaziaturevantaggiose -> Aufat::129. spaz=20080 -- 20 1can = 3 -- 20 CalcolodeinodiCCL: portodatesequentecostruzione:Hodivisolintervallofor t] innintervallidiangoloti = Posizionedelnodi: :=-cos) 8888⑧88->x= 6 + pe. LommeSef(I) allora,considerando i nodi CGL _ ) polinomiointerpolatore è taredieTu f - o fpern-no-> L' i n te r p o l a z i o n e é convergente INTERPOLAZIONELINEARECOMPOSICA Costruzionedell'interpolantesuddividendolintervallodiinteresse insotto-intervalli eusaredei polinomidigrado bassosuciascunodiessi -Data una funzione eCE) entnodiequispaziat:X......Anin Iho: Nef(x) = f(x) + f(x) - fil/x - x)perxefi Xitz - Xi Evrove. El = mIf()- fall If" am H=E(x)l-CH -> E) - 0,SPLINESCUBICHEInterpolazionecompositechegerantisce un regolaritàdellesoluzimeanchetraduesotto-interval: -> Dgw curvos puòesseredescrittecome S(x) = 0+0x + 2x2 + 2x Def:n setto-interval: _ hen funzioautiche.Inincognite e hn-2equazion: · nt1interpolazioneSy(i) = f(xi) · n - 1continuitàc' e:nod:Sit(Xil = S(xi) · necontinuitoanodi(Site('(i) = (55)(i)Mancanoquind:2equazio · n-scontinuito(elhed:(Sat"(i) = (55)"(i)Opzione1: Spline naturali:Sa"(Xal = 0 S/Xnl = 0Opzione2:Splinenot-a-Rnot:S,"continue inXeexureErrore: fx-sol= CH canr= gradodiderivazime METODODEIMINIMQUADRATI Vo g l i ocostruireun'approssimazionenoninterpolantedellafunzioneotale cheyi = f(xil-But itspunticercain polinemiedi godeImencheminimizziladistanzedell'approssimentedo (xi.Gil -y-(x)]=(y--paxel] Iclp:approssimate CM Prel": inqualunquepolinomiodigode m InMattab:Interpolazionelagrangia e = polyfit/xy.n) de cui ottengo e = de..... ero)Approssimazione aiminini quadrati-ca = polyfit(xy-m) conman "¥ Posso usarem = 1percalcolarelarettadiregressionelineare 6)QUADRATURA INTEGRAZIONESQUADRATURA)NUMERICAScopo:cercolare unapprossimazionedellintegrarediunafunzioneIntaleche: In=deffeldxOpzione1:Formuladelpuntomedio.In Ipn = (6 - wf(m) cmm = e -Errore:F - Ipm = f(x)dx - 16 - a)f(m) -(f(x) - f(m)]dxEs f(m)(x - m)UsoespansionediTa y l o r centratoinm: f(x) = f(m) + f((m)(x - m) + ff"(exx)(x - m)2cma=(xm) * Lerroredivento: (f(m)(x - m)dx + (zf"/E(x))(x - mdx=1FzF1 = (f(m)(x - m)dx = 0pachele areeadestraea sinistra sicompensanoconvalori opposti 6 6 =2 = 2f"(((x))(x - m)2 = Ef"(n)((x - m)dxcmy = (b)datoda fegd=f(a)!ga 3 cmxc(2,6) -Epm = fz = f "(n)(6) - Epel f Opzione2:Formuladetrapezio:1 = It = =(f(x) + f(6)) -> Errore:Analogamenteall'opame1ottengo: Et =- f") -> Et "A l l &pzime3:FormuladiSimpson:1 = Is = 6(f() + (f(m) + f(b)] -> Errore:Analogamenteall'opere1ottengo: Es =- ti f -> IEslE D if" ilINTEGRAZIONECOMPOSITASuddivido(a.6] in n-seteintera. Incui Fi = (xi-e.) i = 1... - x = etitH = f - b)/u -> Possoapplicareunaformuladiquadrature suogniintervale · Formuladelpuntomediocomposite. Ior = Hef(x) · Formuladei trapezicomposito:ft = (f(x a + f(x)) = (f(x) + f(6) + HEffil . FormuladiSimpsoncomposite:Is = (f(x) + hf(xx) + f(x)) Ordinedierauratezza:Seuna formuladiquadrature é talecheIE=11-Il = CHP -> LaformulahaordinediaccuratezzapariepGradodiesattezza:Il massimogradodeipolinomichesonointegratiesattamentedaune formuladiquadrature -> Uneformulehergradodiesattezze sef(p)=Fup)Fp=IP Erroreformulapuntomediecomposite: E = f- = fedx - Hf(x) - E a XiekiX-xis=HFi - EpiEnlf"Alef"=fb-e) - c -> Sofeclod)alloraEpin= ch:Ordinediaccuratezza = 2Gradodiesatezza = 1poiché per unafunzionelineareIf"A l l = 0 - c =s- >Epn = e Erroreformuladetrapezi:Andogementetrove:IEtl= lf" IH=al -> Ordinediaccuratezze=2Gradodiesattezza=1 ErroreformuladiSimpson:Esteno lf"KIIH"=ch" es FORMULDIQUADRATURAINTERPOLATORIAUnagenericaformuladiquadraturapuòesserescritte come: Fnifl=Eadquadrature -> Orainvecediapprossimerelintegraledif(x)approssimefix) odin polinomiopiù fraledaintegraveFormuleinterpolatorie:Datideipolinomidi gradonLi _ posso scriverelinterpolantedif come Tn f ( x ) = {f(xi)(i)di, indip.dafRiscrivelaformuleprecedente: Fulfl=t fade=flex-fkl ddikex Possodimostrarechetratuttelepossibiliformulediquadratureinterpolatorenepossetrovare unachegarantisceigradomassimodiesattezzafissatoilnumerodiintervallinDetwisce:peinoni diLegendre:Lok) = 1(e(x) = x (rek) = 2 La let -Proprietàdiortogenerité: (24jk)Lik)dx = (1 perj = i "¥ Oper; fi -faf) = anf(x)sfide con edile ha gradodiesattezzemassimo.Ossic2ntperinfissato Dimostrazione16Laformuladiquadrature Enif)=eiffel=flex hegradodiesatenzaparie n+msee solo seé ditipe intädatorie -> Inoltre seilpolinomiohedde Wa n ( ) = _ k-xl é taepercui: (wn(x)p(x)dx = 0 Xp(x)(p4 1Alloveilteoremefornisceilrisultatoottimate - ilmassimevaloreassumibiledemente -> ossiaquando Winex) è proporzionare al polinomidiLegendrefinoegradomen pachedalleproprietadiortognelitodeipolinomidi Legedre - Lnte é ortogonale e tuttigliLe con ken Ente/Ludx = 0 - (Lupueex = 0 Tr = e...-> Luparklex-shmehikex = (((x)()dx = e Ivalore massimo di i éassuntequandoWireèproportiere er Lune -> Wa re = CLn Xwm(predx = c(nek)pre)dx = c kpelpdorem = neinstato peto al Gradodiesattezze massimo = htm = 2 n+1 reFORMULEDIQUADRATURADIGAUSS Formulediquadratureinterpolatoriedelleformefa = 2if(xi) -> Inodie pesi sonodefiniti dagli zeriedagliaidatidaipolinomidiLegendrenell'intervallo-1-1]:Xi=zeridi(ne(x) 2i=0....nai = (1 - xi)(n + 2/xi))Gradodiesatezza massime = 2n+1Perintegrareesattamenteunpolinomio pelpdero usoveunaformulacon3 = 2n+1 ->n = 2 7) DIFFERENZIAZIONENUMERICA Considerafio.6-Rdifferenziabile can continuiteinfe.6]-Alloraesiste:f(x) = f(x + h) - f(x)kxc(06] hIdea:Approssimareladerivato conilrapportoincrementared _ f 1)Consideroladifferenzefinite in avanti:16 + f)(x) = f(x + h) - f(x) = f(x) ·h-..... In -Percalcolareterroresviluppoo inseriedi Ta y l o r :f(th) = f(x) + (x - x)f(x) + E(x - x)f"()cmde(k.i + h)eh = x - x >Errore = (ex) = (18f((x) - f())=) f(x + h) - f(x)**) + 2x) + 2hf"(3) - fx) - f(x) = 1 - f(x) ="¥ A =(Ehf"/3) = Ewalf)lhech - Ordineeaccuratezze = 1SviluppandoTa y l o rfinealterzoordine avreiottenuto(en1=(Ehf")+ ff"rel)=ch noninfluenteperipiccoli2)Cansiderequind:ladifferenzefiniteall'indietro:(((((x) = f(x) - f(x - h) = f(x)h -> Andogementesvolgo: seriedi Ta y l o r : f(x-h) = f(x) - hf(x) + ghf"(a)(d=( - hx] "¥ (e-1-.... =) - 24f"() = Erfelh = ch - OrdinediaccuratezzeI3) considero una differenzafinitocentrate in. 16f((x) = f(e + h) - f(x - h)24Sviluppoentrantifattori emTa y l o rfinoalbordinefreth) = f(x) + 4f(x) + 2hf"(x) + If (2)fre-h) = f(x) - 4f(x) + 2hf"(x) - 2 f() I Errore:led = feth) fa-h) - f) = selthel+h) - fe) -Ef")+ - f24 = Ef() + f (r))hEchreretezz = 2 Possoapprossimareanchelederivatesuperioriallaprime.f"(x) = mf(x + h) - f(x)freth) - f(x) - f(x) - f(x - h)f(x + h) - 2f(x) + f(x - h)h -( hhh1 = h2=(5f)() (f + fl18 - f)SviluppoconTa y l o rfinealquartogradefreth) = f(x) + hf() + h") + f () + 2hf"/2) cmx=dx+hfre-h) = f(x) - hf(x) + 2hf"(x) - If () + 2hf(y)cm - h = y =xEvrove:(20) = (15f((x) - f"(E)) = f(eth) - 2f(x) + f(x - h) - f(x)) = h =Ehf"() + ") + h"(f) + f/2)] - f") = Elfh = ch 42·Ordinediaccuratezza = 2(Accuratezzaquadratical9) EQUAZION:DIFFERENZIALIORDINARIE Considerailseguenteproblema incuicercolafunzione y dipendentedatefor te) -> (y(t) = f(ty(t)) cm feg. eldat: (yt) = 5. -> PROBLEMADICAvariyRisoluzionenumerica: suddivide=Horty] inNsotto-intervallididimensione:h = Ete definiscegliistantidiscreti:tn=tr + nhchiomeUnlopprossimazionedi y allistentetu: Una gita)--ya percomedite · MetododiEulere in eventirunz-Un = f(trun) -> /Une = Unthf/trun) h · Eulevoesplicite IV. = J.1...-Ottengo:vaor:(VoUs.....Un cheapprossimenolarealesoluzione y · MetododiEulevoall'indietro: (un=fitum.UnalEnfatriere treme · EulevoesplicitoLuo = j. generalmentenon lineare "¥ Algoritmopiùcostose · MetododiCrank-Nicolson:Utilizzo unamediadelleduefunzioprecedenti/Unts-Un _ f(tn.Un) + ftaz-Unra) /Un =un + /f(tn-Un) + f(tute-Un + s)]n2 I v = 5. => (v. = 5. "¥ Metodo implicitoperchédevorisolvere un problemanolineare -> Devivoilmetodotramitequadraturenumerica y(t) = f(ty(t)) - gret = tgelettoreper gen integreeUnte - Un = (f(tn-Un)+freazunrel] Unte= Untf(trub+f(ta-Unsl] Definizionegeneralecanof lometodo:(Un =un + h/Af(tre.une) + (1 - A)f(trun)]confere(V. = 5. -> A = 0:Eulereinavanti -> A = 1.Eulevoaindietro ->A = 12:Crank-NicolsmCONSISTENZASTABILITA ECONVERGENZAConsistenza:considereimetododiEuleroesplicito e valutoende si ottienesostituendolasoluzioneesatonelsistemaUne = Unthf(tuun)ay(tnz)=y(t) + hfftnyful) lasolu nosoddisteloschemenumericeentr = (h)Sviluppoy can Ta y l o r :y(tur)=y(t)+hf(tury(t)) +hf'Eg(a)) ca aeftatural-Definisco errore ditrancamentolocaleente taleper cuievr =hime /ture) - Une = y(tn)- Untheus-Definisceanchel'erroreditrancementoglobare i come. N 12 = Go + e DefinizionestabilitàUnmetodonumericaperlarisoluzionediunproblemsdicouchy e dettoZero-stobile seesistencheso. e Eosotalidaperognihereho] e perogni2= (0.20) se (pul=Eallows: In-zul = c& En = e.....N -> Se un metodoézes-stabile.IUn-zul rimere limitatepertuttipassitemporaiTe o r e m a17:Lex -Richtiger Unoschemealledifferenzefiniteconsistenteperun problemadeipostodeerduzimeéconvergentesee solo seé zero-stabileANALISIDICONVERGENZADefinizione:convergenzaUnmetodonumericoperlarisoluzionediunproblemsdi Couchy é dettoconvergentese: mly(n) -un) = 0 Fn = 0....NInparticolare se: Iyftu)-Unlache diremocheilmetodoconvergecon ordinephoordinediaccuratezzapAnalisidiconvergenza delmetododiEuleroesplicitoIntroduceuncometosoluzionecheotterresepossonpartendodallasoluzioneesattoapossen - 1:un* = y(t ) + hf(tagy(tm)) y(tu)-with-ce,e -> Levoredivente er = (y(t)-u] + (un*-un]Ilmetodoconvergese: t-unhee, eeurovedepropogazionedeglierroritu-e2traccumulatifinewtwe (yf)-rit] -- Sviluppoy ca Ta y l o r : gly yethyzs", treeAlloray(n)-r*(tu) = y(tuz) + hf(tasy(tue)) + fly"(2) - y(tu-)-hf(tasy(tra)) I Eg"() = h(2hf"(a) ~ uh) erroreditroncamentolocateEuroveditrancementoglobae:eihl = newlandll= Ehrly"tl= ch·IlmetododiEulere in avantièconsistentealprimordine - wh)convergeazero funt-un]--Richiedechef sie Lipschitzioneun secondoargemente essi deesisteLiataleche:(f(tyz(t)) - f(tyz(t))) = ((ye(t) - y|t))ft =SfruttandoquesteproprietàottengeIt-un) = (y(tn - 2) + hf(tn-ery(tne)) - Uns+hf/tae.unell=(y(ture) - Un+ h(f(tny(t)) - f(tre.Une)]IE =(y(t) - Un el + h(lyture) - Unrel = lenel + hLlewel=11thh)lenel Calcolequindierroretotale:(en) = ((y(t) - v2 ] + (u - un)) = (y(t) - ul+/un*-un)=he(h) + lethtl/ene = =he() + (2 + h))(h(x) + (1 + h))(enz)] x... ehe(h)(1 + (2 + h)) + ... + (e + h) - ] = =h=(h)(n + h))" - 1 =eh)(e + ht!" - 1 See -1 e y(t) - vo = 0) hL "¥ x - 1 Aquesto puntostruttoladisuguaglianza1 + x xe-1 + h)= eh) -> lenl = (h)/2thL)" - 1=- (h)e - 2 = ein)ettteto - 1 = Meh)L 1 In cui nondipendedah -> (ehll=chlenkMch = ch -> IlmetododiEulere ineventiè convergenteelprim'ordine/covergenzelinesvelAnziogamenteperilmetododiEuleroall'indietro:leal chInfineperimetodoCrank-Nicolsm:lentechiandamentoquadratico) -> Imetodivisti sono dettiad un passoe hannolaproprietàdi essereZero-stabili seconsistenti -unmetodoedunpassoconsistenteé convergenteper ↓ teoremaLax-RichtigerASSOLUTASTABILITA - Studiodellestabilitàsuintervalli illimitatiDefinizione:assolutastabilitàUnmetodonumericoperlasoluzionedi unproblemadi Carchy è assolutamentestabilese,dato un passoh.Atlegenun = 0 quandometodo e applicatoalproblemamodello·Problemamodello: (y(t) = xy(t)canx = e (yfol = 1 -> soluzimeesate: y(t)=eit ConsidersEulers inavantieloapplicaalproblemamodello(vo = 1): n + 1Un = Un + hf(tnUn) = Untharn=lethdlun=11thlune = (1 + hx) - Eulere inavantigenera lasequenzadisoluzioni Un = 11+ 1h)" - mun = (2 + xh)" = 0= (2 + xh) = 1Andizzo I casi: 1)lth = 1 - 1h = avaleperognihEuleroin eventi è stabile2)1 + 1h x - 1 - >1hx - 2-h = assolutamentesoloperhsufficientementepiccoli -> IlmetodoèdettocondizionatamenteassolutamentestabileConsideroEuleroall'indietroapplicatoaproblemamodelloUnte= Unthf(tae.Une) = UnthXUne -> 11 - hx)Un+2 = Un-> r = nun = (enPuz-...(En= (Ent ImetodorisultaincondizimetamenteassolutamentestabileSvolgocalcolianaloghiperCrank-Nicalson:Un= Unt(f(trun)+f(tas _ unel] n + 1 =Un + (un + un+e) ->Unre= Itu=...- te e↑> munto theMetodoincondizionatamenteess.Stabile)L = 1 Lasceltedideve tenercontodelleesigenzediaccuratezza maanchedei limitidestabilità:-Sepervergiodiaccuratezze,hépiccoloalloraconvieneusare Eulereinavantipoiché meno costoso e comunquelimitatoinh -> SepossoscegliereunagrandealloraconviereEuleroimplicite SISTEMIDIERUAZIONIDIFFERENZIALIORDINARIEye/t) = 0.1·Espressi come: (yett) = falt-yett).yar th....ym(t))(yzt) = yazyilt) = fz(t-ye(t)-ye(t) - ...ym(t)) 2c -- I gin(t) = fat-ye(t)-ye(t). ....ym(t)) I Guit) = Yo mRiscrive in modocompatto:I(t) = (ye(t).....yuft))Art-y(t) = (fzt-y(t)....fat - g(t))]+30 = 1y. . . . . .Gand -> (t) = f(tq(t))(y(t) = ya Possoapplicare:metodivistinel cosescalore(f-metodo:24=2 + h(ff( ++2 ( ) + (1 - A)f(t)] cam = ruve....un -> Leproprietà diconsistenze,zero-stabilità econvergenzesonoidentichee cose scature comeleproprietàdiassolutostabilità I datocondizionediassolutastabilitàIlproblemmodellogeneralizzatodiventa. (((t) = J(t)y(t) -perEulereesplicito: (It = 1. h = cx = t/5) roggiospettralePerEuleroimplicitoho.=thet wh+2)Sist.deq. NONlineariinI n+ 1 -> perrisolvereutilizzoduecicliannidati: quelloesternerisolve:passitemporer:quellointernerisolveilproblemanonlineareadesempio conilmetododiNewton EQUAZIONILINEARI DIORDINE mHoiseguenteproblemsdi Carchy:(y"(t) = f(ty(t).y'(t) -...-yk - z(t)y(t) = 5.puòessereviscuito come I y'ltd = ' iWy(m - e)() = (z - e↓ /wert)=y(t) ↑We l t ) = We r t )↑We r t ) = Jawart) = y(t) = wit)We r te l = 'o W3(t) = y"(t) = w2(t) - wat wote e ani I "m(t) = yt) = wi - (t) I whitl = f(twert).....Wme(t)) (Waital-go ·SistemadimEDDdiordine1 ADATTIVITA DIPA S S O "¥ Vo g l oregolareilpassoinbaseall'andamentodellasoluzione -> DeropoterstimareVe r ro reepassoneintrodurrelasequenteregol:see"=ahvoteresee,adevo ridurreh Noncrescendetosoluzioneesattehobisognodiunostimatoredell'errore ConsideroEuleroesplicite.Un = "+hf(tu)(passoh) ->aeconsideralasoluzioneapprossimete conduepassidimezzati :v=uf(tu)vi = wftu) Possoconsideraree unun comeuno stimatoredell'errore METODIDIALTOORDINEI metodiad un passononpossonedareordinidiconvergenzesuperiorio2-Possoalternativamenteusare: metodimultiste, conpiùpassitemporal · metodinon-linearicomeRunge-KuttoMetod:multistep, usmopiù possi temporaliperapprossimare l' oppure fity)·Esempio: Unis-UntUne=hf(tne _ une) - Inquestocasodevocostruireunevein modediverseMetodiRunge-Kuta:metodi apiù stadiimpliciti o espliciti-Esempio,metododiHern:* = Un+hf(trun) Un=Un + (f(tn _ Un) + f(tue)