PA081 Programování numerických výpočtů

Přednáška 3

Sylabus

V rámci PNV budeme řešit konkrétní úlohy a to z následujících oblastí:

• Nelineární úlohy– Řešení nelineárních rovnic– Numerická integrace

• Lineární úlohy– Řešení soustav lineárních rovnic– Metoda nejmenších čtverců pro lineární úlohy– Sumace obecné a s korekcí

• Numerické výpočty v C a C++– Optimalizace výrazů, optimalizace při překladu

Nelineární úlohyatan x / tanh x = b (1)

Výraz tvaru: atan x / tanh x = b

Pro b platí: 1 <= b <

atan/tanh

1

1,05

1,1

1,15

1,2

1,25

1,3

1,35

1,4

-6 -4 -2 0 2 4 6

atan/tanh

Nelineární úlohyatan x / tanh x = b (2)

a) b 1 výraz tvaru: atan x / tanh x = b

Musíme si uchovat rozdíl mezi 1 a b => použijeme substituci b = 1 + ( je malé)

Upravujeme:

atan x = (1 + ) tanh x

atan x – tanh x = . tanh x

atan x . cosh x – sinh x = . sinh x

Teď můžeme použít mocninné řady

2 téměř stejné hodnoty => musíme se jich zbavit

Nelineární úlohyatan x / tanh x = b (3)

atan x . cosh x – sinh x = . sinh x

...!5

x

!3

xxxsinh

53

...!4

x

!2

x1xcosh

42

...5

x

3

xxxtana

53

Nelineární úlohyatan x / tanh x = b (4)

...8113.3x

70064.3x

6.3x

5.31

...!5

x!3

x1

x 642

42

2

...8113.3x

70064.3x

6.3x

5.31

...!5

x!3

x1

x 642

42

4

t = x2; f(t) je kontrakce (alespoň na [-0,2 , 0,2])

iteruji

Iterační metodypro řešení nelineárních úloh

• Hledání pevného bodu:– Metoda prosté iterace

• Hledání průsečíku s osou x:– Metoda půlení intervalů– Metoda regula falsi

• Modifikovaná metoda regula falsi

– Metoda sečen– Newtonova metoda

Iterační metodyhledání pevného bodu II

Princip iteračních metod:Máme výchozí nelineární rovnici:F(x) = G(x)

Vytvoříme z ní rekursivní rovnici tvaru:xi+1 = f(xi ,xi-1, ...,x0)(Musí splňovat podmínky věty o pevném bodě.)

Provedeme iterativní výpočet

Nejčastěji se

využívají rovnice:

xi+1 = f(xi)

xi+1 = f(xi ,xi-1)

Iterační metodyhledání pevného bodu III

Iterativní výpočet:

Zvolíme vhodné počáteční

hodnoty x0, x1, ..., xk:

i := k;

DO

xi+1 = f(xi ,xi-1, ...,x0);

i++;

WHILE (PODMÍNKA UKONČENÍ != TRUE)

Iterační metodyhledání pevného bodu IV

Jaké mohou být podmínky ukončení:

• |f(xi+1) – f(xi)| < MIN_FX

• |xi+1 – xi| < MIN_X

• i > MAX_I

Iterační metody hledání pevného bodu - metoda prosté iterace

Pracuje s rovnicí: xi+1 = f(xi)

Nepopisuje metodu, jak z výchozí rovnice získat rovnici xi+1 = f(xi)

Pouze klade podmínky, které musí rovnice xi+1 = f(xi) splňovat:

Existuje x* D(f) tak, že x* je limitou posloupnosti x0, x1, x2, … pro I .

Iterační metody hledání pevného bodu - metoda prosté iterace II

Příklad:Výchozí rovnice: cos x = bRekursivní rovnice:

Zhodnocení:Výhody: Rychlost konvergence (odpovídá typu funkce)Nevýhody:• Neposkytuje žádný univerzální způsob, jak odvodit

rekursivní rovnici. • Neposkytuje ani metodu pro určení x0.

22ii

1i xt,...

720t

24t

21

et

Iterační metodyHledání průsečíku s osou x - obecně

Výchozí nelineární rovnice:

F(x) = G(x)

Chceme najít x, pro které platí:

F(x) – G(x) = 0

Využijeme metody pro hledání průsečíku s osou x.

Hledáme průsečík f(x) s osou x, přičemž:

f(x) = F(x) – G(x)

Pro hledání průsečíku f(x) s osou x existují standardní metody: půlení intervalů, regula falsi, ...

Iterační metodyHledání průsečíku s osou x – obecně II

Ještě než použijeme standardní metody:

Musíme D(f) funkcie f(x) rozdělit na intervaly:

<ai, bi>, kde i = 1, 2, 3,…

Tak, aby platilo:

• f(x) má v intervalu <ai, bi> právě 1 průsečík s osou x

• f(ai). f(bi) < 0

• f(x) je v intervalu <ai, bi> spojitá

Iterační metodyHledání průsečíku s osou x – obecně III

Máme výchozí funkci f(x) a interval <a, b>

Zvolíme funkci m pro výpočet xi+1:

xi+1 = m(xi ,xi-1, ...,x0)

Funkce m je popsána v rámci metody

pro určování průsečíku s osou x

Provedeme iterativní výpočet

Nejčastěji se

využívají funkce

tvaru:

xi+1 = m(xi)

xi+1 = m(xi ,xi-1)

Iterační metodyHledání průsečíku s osou x – obecně IV

Iterativní výpočet:

Zvolíme vhodné počáteční

hodnoty x0, x1, ..., xk:

i := k;

DO

xi+1 = m(xi ,xi-1, ...,x0);

i++;

WHILE (PODMÍNKA UKONČENÍ != TRUE)

Iterační metodyHledání průsečíku s osou x – obecně V

Jaké mohou být podmínky ukončení:

• |f(xi+1) – f(xi)| < MIN_DF

• |f(xi+1)| < MIN_F

• |xi+1 – xi| < MIN_X

• i > MAX_I

Iterační metodyHledání průsečíku s osou x – Newtonova metoda

Princip:

Vysvětlím na tabuli.

Iterační metodyHledání průsečíku s osou x – Newtonova metoda II

Volba počátečních hodnot: x0

Výpočet xi+1

Vstup: x0

Vlastní výpočet:

)x('f

)x(fxx

i

ii1i

Iterační metodyHledání průsečíku s osou x – Newtonova metoda III

Příklad:f(x) = x3 – x – 1

x0 = 1

x1 = 2

Iterační metodyHledání průsečíku s osou x – Newtonova metoda IV

Zhodnocení:Výhody: • Kvadratická konvergence (v každém kroku se zdvojnásobí počet

platných cifer)

Nevýhody:• Je nutno počítat derivaci• V některých případech nekonverguje (xi+1 může vyjít mimo

interval, kde funkce splňuje dříve uvedené podmínky)

Iterační metodyHledání průsečíku s osou x – metoda sečen

Patří mezi semi-Newtonovské metody – pracuje podobně jako Newtonova metoda, ale místo derivace využívá pouze její aproximaci (směrnici přímky xi, xi-1)

Princip:

Vysvětlím na tabuli.

Obrázek + odvození vzorce:

)x(f)x(f

)x(f.x)x(f.xx

i1i

i1i1ii1i

Iterační metodyHledání průsečíku s osou x – metoda sečen II

Volba počátečních hodnot: x0 = a, x1 = b

Výpočet xi+1

Vstup: x0, x1

Vlastní výpočet:

)x(f)x(f

)x(f.x)x(f.xx

i1i

i1i1ii1i

Iterační metodyHledání průsečíku s osou x – metoda sečen III

Příklad:f(x) = x3 – x – 1

x0 = 1

x1 = 2

Iterační metodyHledání průsečíku s osou x – metoda sečen IV

Zhodnocení:Výhody: • Takřka kvadratická konvergence• Nepoužívá druhou derivaci

Nevýhody:• V některých případech opět nekonverguje (xi+1 může vyjít mimo

interval, kde funkce splňuje dříve uvedené podmínky)

Iterační metodyHledání průsečíku s osou x – půlení intervalu

Princip:

Vysvětlím na tabuli.

Iterační metodyHledání průsečíku s osou x – půlení intervalu II

Volba počátečních hodnot: a0 = a, b0 = b

Výpočet xi+1 (a také ai+1 a bi+1)Vstup: ai, bi

Vlastní výpočet:

IF f(xi+1) == 0konec výpočtu, řešení: xi+1

IF f(xi+1).f(ai) < 0ai+1 = ai ; bi+1 = xi+1

ELSE ai+1 = xi+1 ; bi+1 = bi

2

bax ii

1i

Iterační metodyHledání průsečíku s osou x – půlení intervalu III

Největší nutný počet kroků pro získání hodnoty xn s přesností :

002

ablogn

Iterační metodyHledání průsečíku s osou x – půlení intervalu IV

Příklad:f(x) = x3 – x – 1

x0 = 1

x1 = 2

Iterační metodyHledání průsečíku s osou x – půlení intervalu V

Zhodnocení:Výhody: • Konverguje vždy!!!• Dokážeme určit největší nutný počet kroků

Nevýhody:• Konverguje pomalu (lineární konvergence)

Iterační metodyHledání průsečíku s osou x – regula falsi

Opět semi-Newtonovská metoda

Využívá však stejný posun krajních bodů jako metoda půlení intervalů => zůstane v intervalu a0, b0

=> konverguje vždy

Princip:

Vysvětlím na tabuli.

Obrázek

Iterační metodyHledání průsečíku s osou x – regula falsi II

Volba počátečních hodnot: a0 = a, b0 = b

Výpočet xi+1 (a také ai+1 a bi+1)Vstup: ai, bi

Vlastní výpočet:

IF f(xi+1) == 0konec výpočtu, řešení: xi+1

IF f(xi+1).f(ai) < 0ai+1 = ai ; bi+1 = xi+1

ELSEai+1 = xi+1 ; bi+1 = bi

)a(f)b(f

)a(f.b)b(f.ax

ii

iiii1i

Iterační metodyHledání průsečíku s osou x – regula falsi III

Příklad:f(x) = x3 – x – 1

x0 = 1

x1 = 2

Iterační metodyHledání průsečíku s osou x – regula falsi IV

Problém s metodou regula falsi

Vysvětlím na tabuli.

Princip modifikované metody regula falsi

Vysvětlím na tabuli.

Iterační metodyHledání průsečíku s osou x – modifikovaná regula falsi

Volba počátečních hodnot: a0 = a, b0 = b

Výpočet xi+1 (a také ai+1 a bi+1)Vstup: ai, bi

Vlastní výpočet:

IF f(xi+1) == 0konec výpočtu, řešení: xi+1

IF f(xi+1).f(ai) < 0ai+1 = ai ; fm(ai+1) = f(ai+1)/2 ; bi+1 = xi+1 ; fm(bi+1) = f(bi+1)

ELSEai+1 = xi+1 ; fm(ai+1) = f(ai+1) ; bi+1 = bi ; fm(bi+1) = f(bi+1)/2

)a(f)b(f

)a(f.b)b(f.ax

imim

imiimi1i

Iterační metodyHledání průsečíku s osou x – modifikovaná regula falsi II

Příklad:f(x) = x3 – x – 1

x0 = 1

x1 = 2

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (1)

Prostá iterace:Nalezení rekurzivní rovnice:Nějaké návrhy?

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (2)

Prostá iterace:Nalezení rekurzivní rovnice:

xi+1 = 2 sin xi – 0,1 nefunguje

xi+1 = asin (x/2 + 0,1) funguje:

Je potřeba 18 iterací na 6 desetinných míst

0 0

1 0,100167

2 0,150653

3 0,176237

4 0,189246

5 ...

Prostá iterace:Speciální rekurzivní rovnice:

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (3)

2/x1,0...

!5

x

!3

xxxsin

53

1,0...!5

x

!3

x

2

1.x

42

...!5

x!3

x21

1,0x 4

i2

i

1i

Prostá iterace:Speciální rekurzivní rovnice:

x0 = 0

Je potřeba 4 iterace na 6 desetinných míst

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (4)

...!5

x!3

x21

1,0x 4

i2

i

1i

0

0,2

0,202697

0,202771

0,202773

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (5)

Newtonova metoda:Úprava rovnice:f(x) = x/2 + 0,1 – sin x = 0

Najít v grafu vhodné x0

x0 = 0f’(x) = ½ - cos x

xcos2/1

xsin2/x1,0x

)x('f

)x(fxx i

i

ii1i

Newtonova metoda:

Jsou potřeba 3 iterace na 6 desetinných míst

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (6)

xcos2/1

xsin2/x1,0x

)x('f

)x(fxx i

i

ii1i

0

0,2

0,202772

0,202773

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (7)

Metoda regula falsi metoda:Úprava rovnice:f(x) = x/2 + 0,1 – sin x = 0

Najít v grafu vhodné a0 a b0

a0 = 0, b0 = 1

)a(f)b(f

)a(f.b)b(f.ax

ii

iiii1i

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (8)

Metoda regula falsi:

Je potřeba 6 iterací na 6 desetinných míst

)a(f)b(f

)a(f.b)b(f.ax

ii

iiii1i

0

0,292851

0,205860

0,202860

0,202776

0,202774

0,202773

Iterační metodyPraktický příklad: sin x = x/2 + 0,1 (9)

Prostá iterace: xi+1 = asin (x/2 + 0,1) 18 iterací

Prostá iterace: 4 iterace

Newtonova metoda: 3 iterace

Metoda regula falsi: 6 iterací

...!5

x!3

x21

1,0x 4

i2

i

1i