Numerieke Wiskunde

Examenvragen Numerieke Wiskunde

Hieronder een aantal examenvragen die van een aantal bronnen zijn samengeraapt...
Deze kunnen onduidelijk, onvolledig, onmogelijk,... zijn...
De opmaak is niet altijd helemaal in orde

Oplossingen kunnen fout zijn, daarom volgende aanduidingen:

• NIET NAGEKEKEN: Ter aanduiding van een oplossing, die mogelijk fout is.
• NAGEKEKEN DOOR: <naam>: Ter aanduiding van een oplossing die nagekeken (en indien nodig verbeterd is)

Gelieve mee te helpen in het oplossen (en corrigeren van de vragen). Aanpassingen ondertekenen aub (de voorlaatste knop rechts voegt een handtekening toe).

Examenvraag 1

Gegeven een programma

som = 0.0
for i = 0.0:0.1:1.0
verschil = i - som % == 0
som = som + 0.1

end

Output:

verschil = 0
verschil = 0
..
verschil = 1.1.. e-15

Verklaar waarom het verschil plots niet meer gelijk is aan 0. Waarvoor staat dat getal?
--> Theeft iets te maken met de voorstelling van 0.1 int binair en het verschil in berekening tussen 'sum' en 'i'.

Examenvraag 2

Je krijgt de QR ontbinding van een matrix A, en Q'.b.
gevraagd: ||r|| en hoe zou je x bepalen dat hoort bij die ||r||.
(staat niet in boek, maar in slides bij toepassingen van factorisaties, kleinste kwadratenbenadering)

Examenvraag 3

Je krijgt een paar grafiekjes en maple code over Newton Rapshon en de vereenvoudigde Newton Raphson (niet lineaire stelsels). Je krijgt een 4 tal kleine "verklaar waarom" vraagskes

Examenvraag 4

Maple afdruk: laatste vraag van de examenvragen in de winabundel (Die over het bepalen van eigenwaarden met de methode van de machten).

Uit de matrix A = [2 1 -1; 0 3 -5; 0 0 -2] wordt de dominante eigenwaarde berekend. De startwaarden zijn: [-1.00001 1.00002 1]. Op de grafiek is zichtbaar dat er eerst naar 2 lijkt te convergeren, maar uiteindelijk toch de juiste eigenwaarde 3 gekozen wordt. Het berekenen gebeurd met de methode van de machten met normalisatie.

• Hoe komt het dat er eerst naar 2 geconvergeerd wordt?

Wanneer we de startvector uitdrukken met een basis van eigenvectoren (deze vormen een orthonormale basis) blijkt dat de component van de eigenvector van 2 groter is dan de compontent van de eigenvector van 3, voor de gegeven startwaarde.

• Waarom uiteindelijk toch naar 3?

Tijdens het berekenen van een normalisatie worden er afrondingsfouten gemaakt, waardoor er in de component van de eigenvector horende bij de eigenwaarde 3 toch een waarde komt, hierdoor wordt dan convergentie naar 3 gestart.

• Wat als er geen normalisatie gebruikt zou worden?

De methode zou niet naar 3 convergeren, maar bij 2 blijven hangen.

--RubenV 19 jan 2006 12:06 (CET) NIET NAGEKEKEN

Examenvraag 5

Maple printout
p1=(x-2)(x-4)... (x-30)=PROD(i=1..15)(x-xi) met xi=2*i
p2=p1
uitgewerkt: x15+b14x14+...+b0=SOMi=0..15(bixi) [met bi gegeven constanten]

die twee geplot.
een keer van interval x=2..6
een keer van interval x=6..20
een keer van interval x=20..30
(de fout in het derde interval was veel groter dan in het eerste interval)

#Maple code om te testen
f:= (x-2)*(x-4)*(x-6)*(x-8)*(x-10)*(x-12)*(x-14)*(x-16)*(x-18)*(x-20)*(x-22)*(x-24)*(x-26)*(x-28)*(x-30);
g:=collect(f,x);
#Aangezien ik geen verschil kon zien bij mijn eigen test van de 2 functies heb ik het verschil geplot
plots[logplot]([f-g],x=2..6); 
plots[logplot]([f-g],x=6..20);
plots[logplot]([f-g],x=20..30);

De vraag is hoe het komt dat de fouten groter zijn voor grotere nulpunten. Als bijvraag moest ik verklaren waarom de fout voor vb. x=28 van de orde 10^13 is en van welke orde de fout dan is voor x = 4. ( dat laatste zag je niet op de grafiek, omdat de fout heel klein was tegenover de grootte van de functie zelf ).

Een beetje uitwerking van mezelf, omdat dit niet makkelijk is, en we zoiets niet direct gezien hebben in de oefenzittingen:
noem r(x) de veelterm met coëfficiënten b_i = a_i(1+epsilon_i).
Dan geldt: r(x)-p(x) = som voor i van 1 tot 15 van (epsilon_i*a_i*x^i).
Neem nu epsilon = max epsilon_i. Dan moet je epsilon buiten haakjes halen, en het is dan heel belangrijk en niet voor de hand liggend dat je absolute waarden moet toevoegen in de som, omdat elke epsilon apart zowel positief als negatief kan zijn.
Dus r(x)-p(x) = epsilon* som voor i van 1 tot 15 van abs(a_i*x^i).
Dan ben je er, want dat laatste is groter als x groter wordt en zo.
Voor de grootte-ordes moet je gewoon de grootte-ordes van epsilon en van die som zoeken. Voor epsilon hangt dat af van je getalvoorstelling, en voor de som kan je het met je rekenmachine uitrekenen voor gegeven a_i en x.

Examenvraag 6

Er is een functie van de vorm p(x) = a0 + a1x + a2x^2 + ... +an*x^n (n is niet gekend)
p(0) = 5
p(1) = 9
p(2) = 15
p(3) = 18

Gegeven dat alle gedeelde differenties van de vierde graad 1 zijn.
Geef a3.
Aangezien alle gedeelde differenties van graad vier gelijk zijn aan 1, kan je eenvoudig inzien (gedeelde diff. berekenen) dat al die van graad 5 gelijk zijn aan 0. Je kent dus de graad van de interpollerende veelterm. Dan is het gewoon een kwestie van de Newtonveelterm invullen met gedeelde differenties die je eenvoudig berekent. Een weggevertje dus.

Deze vraag is identiek aan vraag 9 (met andere gegevens weliswaar), uitwerking staat daar.

Examenvraag 7

Maple printout
Newton Raphson.
gegeven: f(x), df(x)
plot van de fout voor a=-1 (naar nulpunt -0.3....)
geef de convergentiesnelheid in detail.

Examenvraag 8

gegeven een 2-dimensionaal lineair stelsel Ax = b met

A = [ (alfa+1)   1  ]
    [ alfa       1  ]

We gebruiken de methode van Jacobi om een nulpunt te vinden. Bepaal alle waarden van alfa waarvoor de methode van Jacobi convergeert ( voor alle startwaarden ).

Oplossing:
0 < alfa < 1 Zie boek pagina 81-82.

• Door te eisen dat de matrix diagonaal-dominant is (maar dit is voldoende voorwaarde, niet noodzakelijke!).
• Door G te berekenen (p. 81) en de norm ervan kleiner als 1 te eisen.

Ben NAGEKEKEN DOOR: --RubenV 19 jan 2006 15:03 (CET) -> lijkt me juist, strikte ongelijkheid

- Lijkt mij fout hoor --Thomas

---

Uitleg bij de oplossing.

We bepalen ||G||2 zo, dat 0<||G||2<1 (||G||2 is de 2-norm van G)

G is voor jacobi -D^-1 *(U+L).

In ons geval is

U+L = [ 0     1  ]
      [ alfa  0  ]

en

D^-1 = [ 1/(alfa+1)     0  ]
       [ 0           alfa  ]

hieruit volgt dat

G = - [ 0     1/(alfa+1) ]
      [ alfa          0  ]

We mogen niet ||G||1 nemen van G, we moeten ||G||2 van G.

||G||2 is (max(eigenwaarden van G^T*G))^(1/2)

We bepalen dus eerst

G^T*G =

[ alfa^2     0            ]
[ 0          1/(alfa+1)^2 ]

De eigenwaarden hiervan zijn de oplossing naar lambda van

det((G^T*G)-lambda*eenheidsmatrix) = 0

de eigenwaarden zijn de oplossingen naar L van volgende gelijkheid

L^2+L*(-(A^2+(1/(A+1)^2)))+A^2/(A+1)^2 = 0

Zei L1, L2 de 2 oplossingen hiervan

dan is (max(L1,L2))^1/2 de 2-norm van G

De gezochte waardes voor alfa zijn de alfas die ervoor zorgen dat 0<(max(L1,L2))^1/2<1

--Thomas

Examenvraag 9

• eem p(x) = a0 + a_1 x + ... + a_n x^n n is onbekend. p(0)=4, p(1)=9, p(2)=15, p(3)=18. De gedeelde differenties van orde 4 zijn allemaal gelijk aan 1. Bepaal a_3.

• (Gedeeltelijke) Oplossing:

Stel dan volgende diff tabel op:

0  4
            5
1  9           0.5
            6       -2/3
2  15         -1.5       1 <= gegeven
            3                   0 <= deze rij is dus helemaal 0, en bijgevolg is de graad 4           
3  18                    1

Vul dan de tabel eventueel achterwaards in voor xi = 4, een veelterm van graad 4 is volledig bepaald door die 4 punten.

uit 4.26 halen we dat de coëf van x^3 = -2/3 + 1 -> moet dit niet -2/3 - 6 zijn? --Ben

immers expand((-2/3)*(x-0)*(x-1)*(x-2)) =

                  2  3      2   4          
                - - x  + 2 x  - - x
                  3             3 

en expand((x-0)*(x-1)*(x-2)*(x-3))=

              4       3       2               
             x  - 6 x  + 11 x  - 6 x

de andere termen hebben geen 3de graadsterm.

---

Uitleg bij de oplossing.

Die elementen op de bovenste rij zijn de coefficieten voor de interpolerende veelterm volgens Newton. Die coefficienten staan tegenover basis 1,(x-x0),(x-x0)(x-x1),...

Wat gevraagd is, is de coefficient die bij x^3, tegenover basis 1,x,x^2,...

Om dat op te lossen, zoekt ge eerst de coefficienten tegenover basis 1,(x-x0),(x-x0)(x-x1),... Ge krijgt dan, p(x) = f[x0] + f[x0,x1] (x-x0) + ...

De f[x0], f[x0,x1], .... verkijgen we door de differentie tabel van hierboven op te lossen.

Dan werken we p(x) = f[x0] + f[x0,x1] (x-x0) + ... uit zodat we iets in de vorm van p(x) = a + b x + c x^2 + ... krijgen

Deze uitwerking gebeurt per term in de interpolerende veelterm volgens netwon De eerste uitgewerkte term is expand(f[x0]) De tweede uitegewerkte term is expand(f[x0,x1](x-x0) enz...

Daarna tellen we alle expands op bij elkaar en krijgen we de interpolerende veelterm tegenover de basis 1,x,x^2,...

Uit die expands zien we dat ben gelijk heeft, de coef bij x^3 is volgens mij ook -2/3 - 6

--Thomas

Examenvraag 10

Gegeven nog een hoop maple-uitvoer. Het gaat over een vijfdegraadsveelterm met een nulpunt in -0.31. Er wordt Newton-Raphson gebruikt om dat nulpunt te berekenen, en je krijgt een logaritmische plot van de fout. De plot is een heel normale, typische plot voor kwadratische convergentie.

De vraag is: verklaar deze grafiek ( van de fout dus ). Wat is de convergentie-snelheid ?\" Als bijvraag kreeg ik \"het aantal juiste beduidende cijfers verdubbelt bij elke stap, hoe zie je dat in de grafiek ?.

Examenvraag 11

Gegeven: A,b en twee berekende x matrices: Ax=b. De resultaten liggen ver uit elkaar. Bespreek stabiliteit van de methodes als machinenauwkeurigheid 10^-15 is.

Examenvraag 12

• Vraag: Veelterm p(x) met p(-1)=p(0)=p(1) en p'(0)=1. Geef alle veeltermen van zo laag mogelijke graad die hieraan voldoen. (Antwoord: p(0)+x-x³)

• Oplossing:

De graad is 3 (2 punten is graad 1, 3 is graad 2, en die afgeleide zorgt voor nog een graad)

We zoeken dus een veelterm van de vorm a3 x^3 + a2 x^2 + a1 x^1 + a0 --Thomas 19 jan 2006 17:04 (CET)

analoog met het stelsel op pag 118 krijgt men

a0 -a1 +a2 -a3 = p(0)   (invullen van -1)
a0 = p(0)               (invullen van 0)
a0 + a1 + a2 +a3 = p(0) (invullen van 1)
a1 = 1                  (invullen van p' en 0)

oplossen geeft:

a0 = p(0)
a1 = 1
a2 = 0
a3 = -1

en dus is de oplossing p(0) +x -x^3

p(0) kan de waarde van eender welke constante aannemen, de oplossing is dus anders geformuleerd c + x - x^3, met c element van R --Thomas 19 jan 2006 17:31 (CET)

NAGEKEKEN Lijkt me juist --Thomas 19 jan 2006 17:06 (CET)

Examenvraag 13

Methode van het midden: bespreek grafiek, slecht geconditioneerd?

Examenvraag 14

Newton-Raphson + vereenvoudigde: bespreek een hele hoop grafieken en geef convergentiefactor en orde.

Examenvraag 15

waarom is 0.1*3 niet hetzelfde als 0.3 (= 0,1 en 0,3 worden niet juist voorgesteld)

Examenvraag 16

Stel de hermite interpolerende veelterm van graad 3 door x_0 (f_0 en f'_0) en x_1 (f_1, f'_1)

Examenvraag 17

Gegeven de methode van Newton Raphson. Verklaar de relatieve fouten grafiek van een willekeurige 5de graads veelterm met 3 nulpunten en geef de convergentiesnelheid (hint: die is 0 )

Examenvraag 18

Methode van de machten: zie examenbundel wina (hint: normalisatie beïnvloedt alleen het niet-overlopen, en NIET de componenten van je x_0 tov de andere eigenvectoren)

Examenvraag 19

Dubbel met examenvraag 5
(x-2)(x-4)...(x-30)
en dan diezelfde uitgewerkt.
De fouten verklaren die optreden bij de uitgewerkte veelterm.

Examenvraag 20

niet-lineaire stelsels, grafieken bespreken.

Examenvraag 21

Dubbel met examenvraag 2
QR factorisatie, Q, R, Q'b, etc gegeven, stond helemaal in de cursus

Examenvraag 22

Dubbel met examenvraag 5
Neem de examenvragenbundel mee, want daar staat de vraag helemaal in uitgewerkt (in het ding da ni in TeX is uitgewerkt). Je hebt een Wilkinsonachtige veelterm. (x-2)(x-47)...(x-18) of zo iets. Als ge die zo in matlab uitvoert, dan is da ne juiste grafiek. als ge die echter eerst laat uitrekenen, dan geeft die fouten. De fouten worden heel groot als x groter wordt. Hoe komt dat? Je moet zeker een uitwerking geven van fouten enzo. Het komt er dan op neer dat de fout drastisch groter zal worden als x groter wordt.

Examenvraag 23

Je hebt de methode van NR om een stelsel van twee niet-lineaire vgln op te lossen. Deze gaat even naar een vreemde waarde op de grafiek. Dit is omdat de startvector dicht bij een waarde ligt waar de jacobiaan singulier is (det J = 0) . Gevraagd is de convergentieorde -en factor gevraagd. Dan heb je dezelfde vgln (ook grafiekjes) van de totale stapmethode en enkelv. stapmeth. Ook is convergentieorde en -factor gevraagd. Je kan die een beetje afleiden uit het grafiekje van de rel. fout. (let op: bij de laatste was da lineair, maar 't was een randgeval of zo iets) De twee grafieken raken, dus zijn het allemaal randgevallen die ge moet geven als oplossing. Bij enkelv. stapmeth.: waarom convergeert da naar het andere punt? -> singulier gedoe van J. Hoe kunnen we dat naar het andere punt laten gaan?-> andere volgorde van vgl oplossen. Een prulvraag waar het vooral op de mondelinge verdediging aankomt.

Examenvraag 24

Je krijgt een willekeurige 8*10-matrix (A), de Q en R ervan. Ook heb je een willekeurige 8*1-vector b. Dan geven ze je Q'b=bt .
Gevraagd: min_(x)||Ax-b||_ 2 tot op twee cijfers na de komma.
Een methode hoe je dit moet berekenen.

Naar 't schijnt iet's met kleinste waarden benadering.

Examenvraag 25

Gegeven is een functie f(x) = sin(x) in het interval (-pi,pi).
Gevraagd : geef een bovengrens op de interpolatie-fout als ge weet dat uw interpolerende veelterm p is die in n-1 interpolatiepunten interpoleert.

--> Gewoon formulekes uit het boek overschrijven + invullen en uitwerken. Gelukkig wordt uw n-de afgeleide sin() dus wordt da 1, Dus hangt die waarde enkel af van (x-x_0)(x-x_1)...(x-x_n). Nu wil hij wel een concrete waarde. Dan moet ge dus inzien dan (x-x_i) hoogsten 2*pi is en dan bekomt ge (2*pi)^n/n!

Examenvraag 26

Gaat over Newton-Raphson en het bepalen van sqrt(a). Ge krijgt een iteratie-functie gegeven. Gevraagd : de functie bepalen die als wortel sqrt(a) heeft. En dan wa analyseren.

--> Oefening in oefenzitting gezien, dus eigenlijk met een paar kleine aanpassingen gewoon overschrijven.

Examenvraag 27

Gegeven een matrix en een startwaarde, bespreek dan wat er gebeurt als ge de methode van de machten toepast daarop.

--> Blijkbaar is de eigenvector die ge uitkomt nul,... blablabla...??

Examenvraag 28

Examenvraag uit eerste oefenzitting

Examenvraag 29

Zij A een matrix waarbij alle elementen null zijn behalve de elementen op de diagonaal en antidiagonaal. Schrijf een algoritme om het stelsel AX=B op te lossen.

Examenvraag 30

Stelsel van 2 niet-lineaire vergelijkingen. Convergentiegetal en -orde bepalen.

Examenvraag 31

Matrix [ a b; c d] met
a = 10^-5
b = 10^-5
c = 3 - a
d = ab - 2 / b

Startwaarde [1; 1]

Zoek convergentiegetal en orde en waarom is er zo'n grote fout?

Examenvraag 32

matrix met op eerste rij a1, a2,..., an en dan op de diagonaal onder de hoofddiagonaal allemaal eentjes en rest van elementen zijn 0.
Gegeven is dat λ₁ > dan alle andere eigenwaardes.
Dan is het volgende proggrammake gegeven;

Kies X^(0) willekeurig
for i = 1 tot n
X^(i) = A * X^(i-1)

Scaleer deze zodat laatste component 1 wordt

Nu moet je bewijzen dat de voorlaatste component naar λ₁ convergeert

Oplossing
Aangezien dit een niet zo makkelijke oefening is, heb ik er een oplossing van gezocht.
Eerst moeten we bepalen waar de scalering aan gelijk is:
C_p * X⁽⁰⁾ is gelijk aan:

[ a_1*x_1 + a_2*x_2 + ... a_n*x_n ] (=f1)
[              x_1                ]
[               .                 ]
[               .                 ]
[              x_(n-1)            ]

En als we dit nog eens doen (en we scaleren met de factor x_n-2(de voorlaatste component!!)) verkrijgen we:

[ f1/x_(n-2)*x_1 + f1/x_(n-2)*x_2 + ... + f1/x_(n-2) ]
[                   f1/x_(n-2)                       ]
[                       .                            ]
[                       .                            ]
[                       1                            ]

Het is dus duidelijk dat dit de juiste scaleringsfactor is!

Nu weten we dat X^(k) = A * X^(k-1) / s^(k-1) (met s de scalering die we telkens doen)
Nog een stap verder wordt dit: X^(k) = A * A * X^(k-2) / (s^(k-1)*s^(k-2)) Als we dit helemaal verderzetten krijgen we dus dat:

  (k)   k    0
 X   = A  * X
       -----------------
                        i
       PRODUCT(i=0..k) s

(1) Dus X^(k) * (PRODUCT) = A^k*X⁰

In boek 2 op p. 99 staat dat bij het berekenen van een dominante eigenwaarde dat A^(k+1)*X⁽⁰⁾ / A^(k)*X⁽⁰⁾ gelijk is aan λ₁ voor k gaande naar oneindig.
Als we dit toepassen op wat we hierboven zijn uitgekomen(nl. (1)) krijgen we dat:
X^(k+1) * (PRODUCT(i=0..k+1) / X^(k) * (PRODUCT(i=0..k)) = λ₁
Nu weten we dat X^(k+1) / X^(k) = 1 (we scaleren immers telkens opnieuw...)
Dus blijft er enkel over dat s^(k+1) = λ₁
Dit betekent dus dat de voorlaatste component gaat convergeren naar λ₁
En dus het gevraagde is bewezen!