Untitled 42

3. Przybliżone rozwiązywanie równań nieliniowych i ich układów 154

a następnie na przyjęciu za przybliżenie rozwiązania a rozwiązania układu równań Ax + b = 0.

Niech AY oznacza macierz o kolumnach j^(l) — y⁰*, _y⁽²⁾ — _y^(l), y^B) —    a AF— macierz o kolumnach .F(j>^<1)) — /’(y⁽⁰⁾), F(y⁽²⁾) — F(y⁽¹⁾),

F(j^(,!)) — i^r(y'^,_l)). Z warunku (3.59) uzyskamy wówczas

AF = A- AY

Ponieważ rozwiązaniem układu równań Ax + b = 0 będzie punkt x = -Ab = -A~'(F{y) - Ay) = y - A~^x F(y)

więc jedna z możliwych wersji metody siecznych może przebiegać następująco:

0.    Wybieramy punkty x⁽~ⁿ\ x^(_n+1),    x⁽⁰⁾ oraz przyjmujemy i = 0

1.    Obliczamy macierze AF⁽ⁱ⁾ oraz AY⁽ⁱ\ przyjmując

yo> _{= x}(/-«o jO) ₌ *('-»+», _yw = _xd)    (3.60a)

2.    Wyznaczamy punkty jc⁽ⁱ⁺¹⁾ w sposób następujący

_X(.+ D ₌ xm _ 4F<ⁱ>[^⁽'>]-^,/’(x⁽ⁱ>)    (3.60b)

3.    Przyjmujemy zamiast / numer i -l- 1 i wracamy do kroku 1 Wzory (3.60) określają tzw. (n + 1 )-punktowq metodę siecznych, gdyż do

wyznaczenia kolejnego punktu w ciągu jc^(I), x^(2>, ... jest potrzebne (n + 1) poprzednich punktów i wartości odwzorowania F w tych punktach. Aby można było posłużyć się wzorem (3.60b), macierz AF^U) musi być nieosobliwa. W przeciwnym przypadku należy w inny sposób wyznaczyć punkty y^u\j = 0, 1, ..., n, rezygnując z części punktów x^(l~ⁿ⁾, x⁽ⁱ\ W tych wybranych punktach y należy obliczyć wartość F(y); nastąpi zatem wzrost nakładu obliczeń w danej iteracji. W skrajnym przypadku macierze AY i A F obliczamy bez korzystania z poprzednio wyznaczonych punktów x⁽ⁱ~^l), x⁽ⁱ~²⁾,x⁽ⁱ~ⁿ⁾; przyjmujemy wówczasy⁽ⁿ⁾ = jr^(,), a brakujące punkty    ...,^⁽⁰⁾ dobiera

my np. zgodnie ze wzorem

y(n-j) _{= X}V) _{+ he}(j)' j ₌ 1( 2> n    (3.61)

gdzie h jest pewną ustaloną liczbą, a wektory e^U) są wektorami przestrzeni R". Metoda siecznych sprowadza się wtedy do dyskretnej metody Newtona, w której pochodną F'(x⁽⁰) przybliżamy macierzą

f f’(x^(,) + he^(,)) — F(x⁽ⁱ⁾)    F(x^<0 + he⁽ⁿ⁾) — F(x⁽'⁾)~]

L h •    h J

Należy podkreślić, że w niektórych przypadkach nie można w żaden sposób wybrać punktów y^<0), y^(,\ ..., y⁽ⁿ⁾ tak, by macierz AF była nieosobliwa. Jeśli np. Fx = Bx + c, gdzie B jest pewną macierzą osobliwą, a c pewnym wektorem, to AF = B AK jest macierzą osobliwą, a zatem przy

dowolnym układzie punktów y nie można obliczyć *⁽ⁱ⁺¹⁾ ze wzoru (3.60b). Z tego względu stosowane w praktyce algorytmy metody siecznych są uzupełnione dodatkowymi warunkami, gwarantującymi niezawodność metody (patrz np. [30]).

Ćwiczenia

1.    Odwzorowanie F: Rⁿ~* R" ma postać

F{x) = \f\(x\, X2, ..., X,,), fl(xl, Xi, ..., X„), .... fn(xi, X₂, ..., X„)]

Uzasadnić, że jeśli f,(x_u x₂.....x„) = x„, to przy dowolnych punktach    ..., y⁽⁰⁾

ciąg punktów x⁽¹⁾, x^<2), ... generowany metodą siecznych ma tę własność, że n-te składowe punktów x^(,>, x⁽²⁾, ... są równe zeru.

Uwaga, (n + l)-punktową metodą siecznych, określoną wzorami (3.60), można w tym przypadku obliczyć co najwyżej n punktów, gdyż dla dalszych punktów macierz AF ma zerowy ostatni wiersz, więc jest osobliwa.

2.    Niech macierze AY i AF mają jako kolumny wektory y^(l) — y^<0), y'²’ — y⁰⁾,

y<-)_y(-t> _oraz F(y^w)-F(y^m), F(y^m) - F(y^w).....F(y^w) - F(y⁽’-'⁾), a macierze AY

i AF mają jako kolumny wektory y⁽¹⁾ -y^|0), y⁽²⁾ -y⁽⁰⁾, ..., y^<n) -_y.⁽⁰⁾ oraz F(y⁽¹⁾) - .F(y⁽⁰⁾),

F(y^n>) — F(y^m).....F(y^w) — F(y⁽⁰⁾). Uzasadnić, że macierze AF i AF są równocześnie osobliwe

lub nieosobliwe oraz że w przypadku, gdy są nieosobliwe

AY(AF)-' = AY(AFy'

Uwaga. Powyższy wynik można uogólnić i wykazać, że porządek punktówy^y*"^-y^<0), za pomocą których obliczamy kolejny punkt x^(,+ nie jest istotny.

3.5. POSZUKIWANIE MINIMÓW FUNKCJI JEDNEJ ZMIENNEJ

W wielu przypadkach zadanie znalezienia minimum funkcji /: /?'-*/?' można sprowadzić do rozwiązania równania f(x) = 0, gdzie f .R —^R oznacza pochodną funkcji /. Może się jednak zdarzyć, że wyznaczenie < pochodnej jest zbyt trudne lub funkcja / nie jest różniczkowalna. Jeżeli funkcja / jest dostatecznie regularna (np. można ją lokalnie przybliżyć wielomianami niskiego rzędu), to można posłużyć się metodami aproksymacyjnymi. Jeśli jednak nie znamy własności funkcji, bezpieczniejsze są tzw. metody podziału, które omówimy poniżej.

Załóżmy, że na przedziale ó> funkcja / ma minimum w punkcie a e <a; ó) i że na przedziale <a, a) funkcja jest malejąca, a na przedziale <a; ó) funkcja jest rosnąca. Taką funkcję przyjęto nazywać funkcją unimodalną.

Lemat. Aby zlokalizować punkt a w przedziale ;ó'> o mniejszej długości niż przedział <a; ó>, wystarczy obliczyć wartość funkcji w dwu punktach wewnątrz przedziału <a; bj.

DOWÓD. Wybierzmy dwa dowolne punkty t, i t₂ takie, że a < t\ < t₂ < b. Jeżeli f(t,) </(t₂), to ae<a; t₂). Jeżeli/(r,) >/(t₂), to ae<r,; b).