Prosjekt 4 – Når målingene ikke passer

Arbeidstid: omtrent 4–6 timer for hele prosjektet.

I uke 3 rekonstruerte vi polynomer fra målinger. Nå skal du undersøke hva som skjer når målingene inneholder støy, og avgjøre om en beregnet tilpasning er pålitelig. Bruk QR og projeksjon fra uke 4 som verktøy.

Oppdraget er å begrunne en metode og en tilpasning med egne forsøk. En liten residual er bare én observasjon; du må også undersøke beregningen og hvordan den tilpassede kurven oppfører seg.

Arbeidsplan

Løype	Arbeid
Kjerne	Del 1–4: vurder en tilpasning, undersøk et sammenbrudd og tilpass polynomer
Valgt fordypning	Del 5 eller del 6: sammenlign beregningsmetoder
Redningsforsøk og rapport	Del 7 og en samlet vurdering

Startcellene lager data og gir noen kodeverktøy. Du fyller selv inn beregningene merket TODO. Før hvert forsøk skal du skrive en forventning. Etterpå skal du vise et resultat og forklare hvilken konklusjon det støtter. Endre én innstilling om gangen, og noter grad, målepunkter, støystørrelse og metode.

Ved behov kan du lese om projeksjon i 4.2, minste kvadrater i 4.5 og polynomer i 4.6. Hintene nedenfor er skjult til du åpner dem, slik at du kan prøve selv først.

Kodeverktøy og kjørerekkefølge

Fellesfunksjonene lastes automatisk på denne siden; du trenger ikke kopiere kode fra prosjekt 3. Kjør startcellene ovenfra og ned. Del 5–6 bruker dataene fra del 4. Når du endrer data, må du kjøre de tilhørende beregningene på nytt.

Verktøy	Hva du får
`classical_gram_schmidt(A)`	Klassisk GS: `Q, R`, uten kontroll av små rester
`modified_gram_schmidt(A)`	Modifisert GS: `Q, R`, med kontroll av små rester
`qr_solution(A, b, metode)`	Koeffisienter, `Q` og `R`; standardmetoden er modifisert GS
`method_report(navn, A, b, c, Q, R)`	En samling kontrollverdier til resultattabellen din

Funksjonene er hjelpemidler for å gjennomføre forsøkene. Du skal forklare hvorfor kontrollene er relevante, og selv velge hva som skal sammenlignes. Modifisert GS stopper hvis en ny rest er for liten til å normaliseres pålitelig.

Kjerne

1. Godkjenn eller forkast en foreslått tilpasning

Gitt: seks målinger og modellen \(p(t)=c_0+c_1t\). En foreslått tilpasning har \(c_0=0.95\) og \(c_1=1.10\).

Undersøk: Er dette den beste tilpasningen i minste kvadraters forstand? Hvilke beregninger trenger du for å avgjøre det?

Skriv dimensjonene til \(A,c,b\) og bygg \(A\). Beregn \(r=b-Ac_{\text{forslag}}\) og kvadratsummen av avvikene. Hvilke målinger ligger over den foreslåtte modellen?
Finn en tilpasning med QR. Bruk modified_gram_schmidt(A) til å få \(Q,R\), og beregn deretter koeffisientene selv.
Kontroller \(Q^TQ-I\), \(A-QR\) og \(Q^Tr\) for den nye tilpasningen. Forklar hva hver kontroll undersøker. Gjør også den siste kontrollen for den foreslåtte tilpasningen.
Bruk np.linalg.lstsq(A, b, rcond=None)[0] som kontroll etter at du har funnet din egen løsning. Lever én figur med begge modellene og en begrunnet avgjørelse: Hva gjør du hvis residualen ikke er null, men QR-kontrollene er gode?

Når du vil samle alle elementene i en matrise \(E\) til ett kontrolltall, bruker du Frobeniusnormen: \(\lVert E\rVert_F=\sqrt{\sum_{i,j}E_{ij}^2}\). I Python er dette np.linalg.norm(E, "fro"). Små avvik fra null i kontrollene skyldes avrunding og er forventet.

Hint: modellen og QR

Rad \(i\) i \(A\) er \([1\ \ t_i]\). Fra 4.5 har du \(d=Q^Tb\) og \(Rc=d\). np.linalg.solve(R, d) løser det siste systemet. Pass på at residualen beregnes på nytt for koeffisientene du kontrollerer.

2. Finn årsaken når beregningen svikter

Gitt: en ny matrise \(B\) og de to GS-funksjonene. Undersøk: Kan alle tre kolonnene gi hver sin ortonormale vektor?

Før du kjører koden: Finn en eventuell sammenheng mellom kolonnene, og forutsi hva som skjer med diagonalverdiene i \(R\).

Knytt resultatet til sammenhengen mellom kolonnene som du fant. Identifiser den konkrete divisjonen i GS som må undersøkes; se eventuelt algoritmen fra 4.3.
Sett elementet i tredje rad og tredje kolonne til \(\delta=10^{-4},10^{-10},10^{-16}\), ett forsøk om gangen. For hvilke verdier er kolonnene uavhengige på papir, og når fullføres beregningen?
Den modifiserte funksjonen har en stoppkontroll som den klassiske mangler. Hvilken del av forskjellen du observerer skyldes denne kontrollen?
Vurder påstanden: «Alle verdiene i \(Q\) er endelige, derfor er QR-faktoriseringen pålitelig.» Bruk kontrollene fra del 1 som begrunnelse.

Hint: hva betyr «for liten rest»?

Stoppgrensen i hjelpefunksjonen tilpasses størrelsen på matrisen og presisjonen i flyttallsregningen. En stopp betyr at funksjonen ikke godtar resten som en pålitelig ny vektor. Stoppen er ikke et bevis på at kolonnene er nøyaktig avhengige.

3. Undersøk hva flere målinger bidrar med

Vi går nå over til polynomer. Gitt: et referansepolynom av grad \(3\) som vi lager støyfylte målinger av. Referansen er kjent i forsøket, slik at vi kan kontrollere resultatet. Selve tilpasningen skal bare bruke målepunktene og de støyfylte målingene.

Matrisen med Chebyshev-verdier

Vi skriver modellen i Chebyshev-basis:

\[p(x)=c_0T_0(x)+c_1T_1(x)+\cdots+c_nT_n(x),\]

der

\[T_0(x)=1,\qquad T_1(x)=x,\qquad T_{j+1}(x)=2xT_j(x)-T_{j-1}(x).\]

Chebyshev-målematrisen \(C\) inneholder verdiene av disse basisfunksjonene ved målepunktene: rad \(i\) hører til \(x_i\), og kolonne \(j\) hører til \(T_j\). Altså er \(C_{ij}=T_j(x_i)\). For grad \(2\) ser matrisen slik ut, siden \(T_2(x)=2x^2-1\):

\[C=\begin{bmatrix} 1&x_0&2x_0^2-1\\ 1&x_1&2x_1^2-1\\ \vdots&\vdots&\vdots\\ 1&x_{m-1}&2x_{m-1}^2-1 \end{bmatrix}.\]

Dermed inneholder \(Cc\) modellverdiene ved de \(m\) målepunktene, akkurat som \(Ac\) i linjeforsøket. Grad \(n\) gir \(n+1\) koeffisienter og en matrise med \(m\) rader og \(n+1\) kolonner.

Kodeverktøy	Bruk
`chebyshev_matrix(points, n)`	Lag \(C\) for målepunktene og graden
`cheb.chebval(points, c)`	Beregn polynomverdier fra Chebyshev-koeffisienter
`reference_coordinates(n)`	Lag et fast referansepolynom av grad \(n\)

Hvor mange likninger og ukjente har du? Beregn første rad i \(C\) for hånd, og kontroller den mot koden.
Gjennomfør tilpasningen. Registrer residualnormen og den største absolutte forskjellen mellom tilpasset kurve og referanse på grid. Hvorfor må begge størrelsene undersøkes?
Hold \(m=12\) fast og prøv noise_size lik \(0\), \(10^{-3}\) og \(10^{-2}\). Hva endrer seg i tilpasningen og kontrolltallene?
Hold støystørrelsen fast på \(10^{-3}\) og sammenlign \(m=8,16,32\). Gjenta med frøene \(2026,2027,2028\). Er konklusjonen om flere målinger den samme i alle forsøkene?

Når antallet målinger varierer, rapporter også \(\lVert r\rVert_2/\sqrt m\): kvadrer avvikene, ta gjennomsnittet og deretter kvadratroten. Dette gir et mål på avvik per måling. Bruk én liten tabell til å sammenligne forsøkene; du trenger ikke en figur for hvert frø.

4. Samme målinger, to forskjellige basiser

Gitt: ett polynomrom, ett sett punkter og én målevektor. Undersøk: Har basisvalget betydning for den beregnede kurven?

Monomialmatrisen \(M\) har kolonnene \(1,x,\ldots,x^n\) evaluert ved målepunktene; Chebyshev-matrisen \(C\) har kolonnene \(T_0,\ldots,T_n\). Begge beskriver polynomer av grad høyst \(n\). Koeffisientene har ulik betydning, så hver koeffisientvektor må brukes med riktig basis når du beregner kurven.

Skriv først hva du forventer: Ville de beste modellverdiene ved målepunktene vært like med de to basisene i eksakt regning? Begrunn.
Beregn tilpasningene med modifisert GS, og lag én figur som viser den absolutte kurvefeilen for hver basis. Registrer også residualnorm, ortogonalitetsfeil og relativ faktoriseringsfeil.
Gjenta med de støyfrie verdiene exact_values. Hvor mye endres hver beregnet kurve når den lille støyen legges til?
Bruk lstsq på de samme to matrisene som kontroll. Hva sier resultatene om hvor mye måledata, basisvalg og beregningsmetode betyr? Ikke anta at én basis alltid gir den beste kurven.

Selv om forskjellige målepunkter gjør modellkolonnene uavhengige på papir, kan små endringer i målinger eller avrundinger påvirke beregningen mye. I denne delen beskriver du følsomheten med de endringene du faktisk måler. Du trenger ikke et nytt matrisebegrep for å gjøre det.

Kontrolltall til tabellen

method_report beregner residualnorm og avvik per måling. Hvis du også gir funksjonen \(Q,R\), får du:

Kontroll	Hva som undersøkes
\(\lVert Q^TQ-I\rVert_F\)	Hvor godt de beregnede kolonnene er ortonormale
\(\lVert A-QR\rVert_F/\lVert A\rVert_F\)	Hvor godt produktet gjengir den opprinnelige matrisen
`alle_endelige`	Om koeffisienter, residual og faktorer inneholder ugyldige verdier

Bruk henholdsvis \(M\) og \(C\) som \(A\) i kontrollene. Én liten kontrollverdi erstatter ikke de andre kontrollene.

Velg én fordypning

Del 5 undersøker selve ortogonaliseringen. Del 6 undersøker en annen måte å løse tilpasningsproblemet på. Begge bruker forsøket fra del 4 som utgangspunkt.

5. Når betyr GS-varianten noe?

Her undersøker du om forskjellen mellom GS-variantene vokser med graden. Sammenlign klassisk GS, modifisert GS og lstsq for gradene \(n=8,12,16,20\). Bruk \(m=2(n+1)+1\) jevnt fordelte målepunkter, samme referansepolynom for begge basisene ved hver grad og støy av størrelse \(10^{-10}\) med fast frø.

Lever en tabell og et plott av ortogonalitetsfeil mot grad. Velg så ett av spørsmålene nedenfor, og undersøk det nærmere:

Er en liten faktoriseringsfeil tilstrekkelig til å stole på \(Q\)?
Følger endringer i ortogonalitetsfeilen endringene i kurvefeilen?
Er metodeforskjellen den samme i begge basisene?

Konklusjonen skal vise til egne tall. Unngå å formulere en generell garanti ut fra ett forsøk.

6. Hva endrer normallikningene?

Fra residualbetingelsen \(A^T(b-Ac)=0\) kan du samle de ukjente i et kvadratisk system.

Skriv dette systemet selv. Hvilke dimensjoner får matrisen og høyresiden?
Implementer løsningen med np.linalg.solve.
Sammenlign med QR og lstsq, først for grad \(12\), deretter for \(16\) og \(20\). Lag dataene på samme måte som i del 4, med \(m=2(n+1)+1\) for hver grad.

Et mål på følsomhet, når vi trenger det

Kondisjonstallet beskriver hvor ulikt matrisen skalerer koeffisientvektorer i forskjellige retninger. Et stort tall varsler at noen endringer i koeffisientene nesten ikke synes i modellverdiene. Da kan små endringer i data eller avrundinger få stor betydning for de beregnede koeffisientene.

Vi bruker varianten som skrives \(\kappa_2(A)\) og beregnes med np.linalg.cond(A). Verdier nær \(1\) betyr jevn skalering; svært store verdier varsler følsomhet. Tallet er ikke den faktiske feilen i koeffisientene eller i den tilpassede kurven.

Hva betyr senket 2 og spektralnorm?

Senket \(2\) viser at vi bruker vanlig euklidsk vektorlengde. For en matrise definerer vi

\[\lVert A\rVert_2=\max_{\lVert z\rVert_2=1}\lVert Az\rVert_2.\]

Dette kalles spektralnormen: den største faktoren matrisen kan forstørre vektorlengden med. Når kolonnene er lineært uavhengige, er

\[\kappa_2(A)= \frac{\max_{\lVert z\rVert_2=1}\lVert Az\rVert_2} {\min_{\lVert z\rVert_2=1}\lVert Az\rVert_2}.\]

Det er altså forholdet mellom den største og den minste skaleringen. Spektralnormen er en annen matrisenorm enn Frobeniusnormen vi bruker til QR-kontrollene. Du trenger ikke beregne disse maksimums- og minimumsverdiene selv.

Et frampek til uke 5: Egenverdier beskriver hvordan en kvadratisk matrise skalerer vektorer langs bestemte retninger, kalt egenvektorretninger. Forbindelsen til kondisjonstallet går gjennom \(A^TA\), som er kvadratisk selv om \(A\) er rektangulær.

Den største og minste egenverdien til \(A^TA\) er kvadratene av den største og minste skaleringen til \(A\). Skriver vi disse egenverdiene som \(\lambda_{\max}\) og \(\lambda_{\min}\), får vi

\[\lVert A\rVert_2=\sqrt{\lambda_{\max}},\qquad \kappa_2(A)=\sqrt{\frac{\lambda_{\max}}{\lambda_{\min}}}.\]

Her er \(\lambda_{\min}>0\) fordi kolonnene i \(A\) er lineært uavhengige. Dette knytter følsomheten til stoffet om egenverdier som kommer neste uke. I dette prosjektet bruker du fortsatt \(\kappa_2(A)\) som et følsomhetsvarsel og beregner tallet med np.linalg.cond(A).

For uavhengige kolonner gjelder \(\kappa_2(A^TA)=\kappa_2(A)^2\) i eksakt regning. Bruk dette som støtte når du tolker forsøket: Hvilken sammenheng ser du mellom følsomhetsvarselet og feilen du faktisk målte? Kondisjonstall beregnet med flyttall kan avvike fra denne identiteten, særlig når tallene blir svært store.

Hint til systemet

Gang \(A^T\) inn i parentesen og flytt leddet med \(c\) til den andre siden. Systemet har \(A^TA\) som matrise. Bruk koden fra del 2 som mønster for å registrere en eventuell LinAlgError uten å avbryte resten av forsøket.

Selvstendig redningsforsøk og rapport

7. Gjør én begrunnet forbedring

Ta utgangspunkt i et forsøk fra den valgte fordypningen der resultatet var mindre pålitelig enn bibliotekets løsning. Hvis du ikke fant en tydelig forskjell, prøv grad \(24\) med \(51\) jevnt fordelte punkter og klassisk GS i monomialbasis. Kontroller resultatet før du velger tiltak.

Velg én endring: metode, basis, polynomgrad, antall målinger eller plassering av målepunktene. Skriv hvorfor du forventer forbedring, og gjennomfør et før-og-etter-forsøk.

Hold referansepolynomet fast, også om du endrer modellgraden. Hvis du endrer målepunktene, lag nye målinger av den samme referansen med samme støystørrelse og fast frø. Bruk minst \(n+3\) forskjellige punkter, modellgrad høyst \(25\) og støy høyst \(10^{-8}\). chebyshev_points(m) gir \(m\) cosinusfordelte punkter i \([-1,1]\); argumentet er antallet punkter, ikke graden.

Rapporter residualnorm, avvik per måling, største kurvefeil på minst 2001 kontrollpunkter og QR-kontrollene når metoden gir \(Q,R\). Dersom du endrer antall målinger eller modellgrad, forklar også hva som gjør sammenligningen rettferdig.

Målet er en dokumentert forbedring. Hvis tiltaket ikke hjelper, skal du vise det og begrunne hva du ville undersøkt videre.

Dette skal leveres

Lever én Quarto-side eller notebook med kjørbar kode. Figurer skal ha aksetitler og en forklaring av hva som sammenlignes. Samle kontrolltall i tabeller, og skill tydelig mellom egne forventninger, observerte resultater og konklusjoner.

Omfang	Leveranse
Bare kjerne	Resultater og korte begrunnelser fra del 1–4
Hele prosjektet	Kjernen, valgt del 5 eller 6, før-og-etter-forsøket i del 7 og en analyse på 400–600 ord

Analysen skal bruke konkrete resultater til å svare på:

Når skyldes avviket at modellen ikke passer målingene, og når tyder kontrollene på problemer i beregningen?
Hva forteller residual, ortogonalitet og kurvefeil hver for seg?
Hva endret du i redningsforsøket, og hvilke resultater støtter vurderingen?
Hvilken begrensning ved forsøket gjør at du bør være forsiktig med å generalisere?

Bruk av kodeassistenter

Du kan få hjelp med syntaks, men du skal selv kunne forklare forsøkene dine. Kontroller at metodene får samme data, og noter hvilke variabler du endret. Automatisk generert kode eller en utskrift alene er ikke en faglig begrunnelse.