Untitled 42

3. Przybliżone rozwiązywanie równań nieliniowych i ich ukiac/ó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 _ y(°\ yM —    ...₍

yn) _ y("~^l\ a AF— macierz o kolumnach F{y⁽¹⁾) — F(y^m), i^r(y^<2)) — F(y⁽¹ >), ^u). Z warunku (3.59) uzyskamy wówczas

AF = A ■ AY

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

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

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

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

y°) _    ,y⁽¹⁾ = x⁽ⁱ~ⁿ⁺'\ _iy⁽ⁿ⁾ = x^(l)    (3.60a)

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

(3.60b)

3. Przyjmujemy zamiast i numer i + 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 x⁽¹⁾, x⁽²⁾, ... 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⁽ⁱ⁾ musi być nieosobliwa. W przeciwnym przypadku należy w inny sposób wyznaczyć punkty y^J = 0, 1, ..., n, rezygnując z części punktów x⁽ⁱ~ⁿ\ ..., x^(,). W tych wybranych punktach j 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^<i_x°~²⁾,x°~ⁿ⁾; przyjmujemy wówczasy⁽ⁿ⁾ = x⁽ⁱ⁾, a brakujące punkty^*"^-0, ...,>'⁽⁰⁾ dobieramy np. zgodnie ze wzorem

(3.61)

yO-J) = _x(‘) + _he(J)' j=\,2,...,n

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^<0) przybliżamy macierzą

Należy podkreślić, że w niektórych przypadkach nie można w żaden sposób wybrać punktów y^o), j⁽¹⁾, ..., y^M 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 AY jest macierzą osobliwą, a zatem przy

dowolnym układzie punktów nie można obliczyć x^u+!) 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) = \fx(x_u Xi.....x_n), f₂(x_u X₂, ..., X„), ..., f,(xI, X₂, .... JC„)]^r

Uzasadnić, że jeśli f.(x_x, x₂, ..., x„) = x„, to przy dowolnych punktach y, y^_l).....y

ciąg punktów x^u), x^<2), ... generowany metodą siecznych ma tę własność, że n-te składowe punktów x^(l), x^<2), ... 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 — y^m, y²⁾ — y, y> — j7<"~') oraz ^^rĆV^<l>) — /^rC>'^<0)), F(y^m) — F{y^w), ..., F(y^M) —    a macierze AY i AF mają jako kolumny wektory y^(,) —y^m, y^m — y^m, ..., y⁽ⁿ⁾ -_£⁽⁰⁾ oraz ż^r(v⁽'⁾) — •F(y⁾), F(y^w) — F(y^(0>),.... Fty¹) — F(y⁽⁰⁾). Uzasadnić, że macierze AF i dFsą równocześnie osobliwe lub nieosobliwe oraz że w przypadku, gdy są nieosobliwe

AY(AF)-' = AY(AF)~¹

Uwaga. Powyższy wynik można uogólnić i wykazać, że porządek punktowy,y^{"~ y^o), za pomocą których obliczamy kolejny punkt x^{(,+ l)}, 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 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 <a; ó> funkcja / ma minimum w punkcie a e <a; i że na przedziale <a, a) funkcja jest malejąca, a na przedziale <oc; h} funkcja jest rosnąca. Taką funkcję przyjęto nazywać funkcją unimodalną.

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

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