Numerieke methoden

[LC02]

”Gegeven a,b ∈ R en f : R2 → R, f(a,b) = a²-ab, bepaal y = f(a,b)”.
a) Bepaal de conditiegetallen van het probleem.
b) Bestudeer de conditie van dit probleem in de volgende gevallen:
A)a = 2.000, b = 1.000, resp. B) a= 2.001, b= 1.000
In beide gevallen neem aan dat de absolute fouten op de input-data zijn |∆a| = |∆b| =
10^−3. In welk geval zijn de relatieve conditiegetallen orde 1? Bepaal tevens in beide
gevallen de relatieve fout op het resultaat.
c) Neem aan dat de input data a en b computergetallen zijn. Voor het gegeven probleem
zijn er twee ”algoritmen” mogelijk:
Algoritme A: u = a ⊖b, v = a ⊗u,
Algoritme B: u = a ⊗a, v = a⊗b, w = u⊖v
Merk op dat de elementaire bewerkingen ⊖ en ⊗ eigenlijk computerbewerkingen zin en
dus een computergetal opleveren,
a ⊗b=(a×b)(1+ε) ≈ a×b, en a⊖b=(a−b)(1+ε)≈a−b,
met verschillende getallen ε die voldoen aan |ε| < eps (eps is de machinenauwkeurigheid).
Welk van de twee algoritmen is stabieler? M.a.w. voor welk van de twee algoritmen is de
relatieve fout op het resultaat kleiner?

[wnvl1]

Gegeven is de functie \( f:\mathbb{R}^2 \to \mathbb{R} \) met
\[
f(a,b)=a^2-ab.
\]
We schrijven ook
\[
f(a,b)=a(a-b).
\]

a) Conditiegetallen van het probleem

De partiële afgeleiden zijn
\[
\frac{\partial f}{\partial a}=2a-b,
\qquad
\frac{\partial f}{\partial b}=-a.
\]

De absolute conditiegetallen zijn dus
\[
\kappa_a^{\mathrm{abs}} = |2a-b|,
\qquad
\kappa_b^{\mathrm{abs}} = |a|.
\]

Het relatieve conditiegetal t.o.v. \(a\) is
\[
\kappa_a^{\mathrm{rel}}
=
\left|
\frac{\partial f}{\partial a}\frac{a}{f}
\right|
=
\left|
\frac{(2a-b)a}{a^2-ab}
\right|.
\]

Omdat \( f=a(a-b) \) volgt
\[
\kappa_a^{\mathrm{rel}}
=
\left|
\frac{2a-b}{a-b}
\right|.
\]

Voor \(b\) geldt
\[
\kappa_b^{\mathrm{rel}}
=
\left|
\frac{\partial f}{\partial b}\frac{b}{f}
\right|
=
\left|
\frac{-ab}{a(a-b)}
\right|
=
\left|
\frac{b}{a-b}
\right|.
\]

We zien dat de relatieve conditie groot wordt wanneer \(a-b\) klein is.

b) Studie van de conditie}

Gegeven \( |\Delta a|=|\Delta b|=10^{-3} \).

Geval A: \(a=2.000\), \(b=1.000\)

Dan is
\[
f=2^2-2\cdot1=2.
\]

Relatieve fouten op de input:
\[
\frac{|\Delta a|}{|a|}=\frac{10^{-3}}{2}=5\cdot10^{-4},
\qquad
\frac{|\Delta b|}{|b|}=10^{-3}.
\]

Relatieve conditiegetallen:
\[
\kappa_a^{\mathrm{rel}}
=
\frac{|2a-b|}{|a-b|}
=
\frac{|4-1|}{1}
=3,
\]
\[
\kappa_b^{\mathrm{rel}}
=
\frac{|b|}{|a-b|}
=
\frac{1}{1}
=1.
\]

Deze zijn van orde \(1\).

De relatieve fout op het resultaat is benaderend
\[
\frac{|\Delta f|}{|f|}
\approx
\kappa_a^{\mathrm{rel}}\frac{|\Delta a|}{|a|}
+
\kappa_b^{\mathrm{rel}}\frac{|\Delta b|}{|b|}
\]
\[
\approx
3\cdot 5\cdot10^{-4}
+
1\cdot10^{-3}
=
1.5\cdot10^{-3}+10^{-3}
=
2.5\cdot10^{-3}.
\]

Geval B: \(a=2.001\), \(b=1.000\)

Dan is
\[
f=2.001^2-2.001\cdot1
=
2.003001.
\]

Nu is
\[
a-b=1.001.
\]

Relatieve conditiegetallen:
\[
\kappa_a^{\mathrm{rel}}
=
\frac{|2a-b|}{|a-b|}
=
\frac{|4.002-1|}{1.001}
\approx
3,
\]
\[
\kappa_b^{\mathrm{rel}}
=
\frac{1}{1.001}
\approx
1.
\]

Ook hier zijn ze van orde \(1\).

De relatieve fout op het resultaat is opnieuw ongeveer
\[
\frac{|\Delta f|}{|f|}
\approx
2.5\cdot10^{-3}.
\]

Dus in beide gevallen is het probleem goed geconditioneerd (orde \(1\)).

c) Stabiliteit van de algoritmen

We vergelijken:

Algoritme A:
\[
u=a\ominus b,
\qquad
v=a\otimes u.
\]

Algoritme B:
\[
u=a\otimes a,
\qquad
v=a\otimes b,
\qquad
w=u\ominus v.
\]

Bij computerbewerkingen geldt
\[
a\otimes b=(ab)(1+\varepsilon),
\qquad
a\ominus b=(a-b)(1+\varepsilon),
\quad
|\varepsilon|<\mathrm{eps}.
\]

In algoritme B worden eerst twee producten berekend en daarna een aftrekking van twee bijna gelijke getallen uitgevoerd. Dit kan leiden tot verlies van significante cijfers (catastrofale subtractie) wanneer \(a^2\) en \(ab\) dicht bij elkaar liggen.

In algoritme A wordt eerst het verschil \(a-b\) berekend en daarna vermenigvuldigd met \(a\). Dit vermijdt het aftrekken van twee grote, bijna gelijke producten.

Daarom is algoritme A numeriek stabieler. De relatieve fout op het eindresultaat is bij algoritme A kleiner dan bij algoritme B, vooral wanneer \(a\) en \(b\) dicht bij elkaar liggen.