Untitled 45

160

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

boków prostokąta, zwanego przez starożytnych Greków „złotym”, stąd nazwa metody.

W metodzie złotego podziału punkty podziału obliczamy ze wzorów

(3.62a)

(3.62b)

(3.62c)

t\^l)= a + (1 — z)(b — a)

/0)=6-(l -r)(b-d)

Jeżeli f(t⁽/⁾) < /(t⁽2^;)), to a pozostaje bez zmian, zaś b =

#+»=/<«

t⁽j'⁺⁰ = a + (1 — z) (b — a)

Jeżeli /(t⁽,°) > /(^2^>), to b pozostaje bez zmian, zaś

u = tf⁰

f((+D _ ;(>+!) _t0+'l=b-(l-z)(b-a), i =1,2, 3, ...

We wzorach (3.62a) celowo zamiast mnożnika z przyjęto mnożnik 1 — z (można bowiem obliczać t⁽2⁰= a + z{b — a)), gdyż powoduje to mniejsze błędy zaokrągleń przy wyznaczaniu kolejnych punktów podziału.

Interesujące jest porównanie efektywności metody Johnsona i metody złotego podziału. Jeżeli zakładamy K obliczeń wartości funkcji (łącznie z wartością w uzyskanym ostatecznie punkcie t), to w metodzie Johnsona

_bm _ _am

należy przyjąć N = K + 1 i wówczas \ t — a| <-. W metodzie złotego

Fk+\

b^m-a^m    /lY'¹

podziału uzyskamy zaś |f — a| ^ —-—-gdzie G, = - 1 . Korzystając

2G*-i    \tJ

z powyższych oznaczeń można uzasadnić, że

(3.63)

2G*_ i < F_k+ i < 2G_k

Zatem, aby wyznaczyć t metodą złotego podziału z dokładnością nie gorszą niż metodą Johnsona, potrzeba co najwyżej jednego dodatkowego obliczenia wartości funkcji.

Ćwiczenia

1.    Uzasadnić nierówność (3.63). Wskazówka. Zastosować indukcję matematyczną.

2.    Minimum funkcji f(x) = |x| jest zlokalizowane w przedziale <0; 8>. Wyznaczyć punkt minimum z dokładnością g = 1 stosując metodę połowienia i metodę Johnsona. Dlaczego metoda połowienia okazała się w tym przypadku skuteczniejsza?

4

CAŁKOWANIE NUMERYCZNE

WSTĘP

Uwagi ogólne o całkowaniu numerycznym

W niniejszym rozdziale rozpatrzymy zagadnienie przybliżonego obliczania całki oznaczonej funkcji jednej zmiennej. Ponieważ wyznaczanie funkcji pierwotnej w wielu przypadkach jest bardzo trudne lub wręcz niemożliwe, stosowanie metod przybliżonych jest więc często konieczne. Ponadto, jeżeli funkcja podcałkowa jest określona za pomocą tablicy, to pojęcie funkcji pierwotnej traci sens i wówczas możemy obliczyć tylko przybliżoną wartość całki.

Gdy przedział całkowania jest skończony, wówczas wiele sposobów przybliżonego obliczania całek polega na tym, że funkcję podcałkową F(x] zastępujemy interpolującą funkcją <p(x), którą łatwo można całkować. Niech cp(x) będzie wielomianem interpolacyjnym Lagrange’a dla funkcji F(x] z węzłami interpolacji x₀, x_u ..., x_N (patrz p. 1.2.1)

N

(p{x) = L_n(x) = X ^<Pk(x)F{x_k)

0^ ₌ (x - x₀) ,..(x - x_k_i)(x - x_k+i) ...(x - x_N) ^k (X_k- x₀)...(x* -**_,)(**-x*_+I)...(x* - X_N)

Podstawiając w miejsce funkcji podcałkowej F(x) wielomian ę(x), otrzymamy

b

b

N

f F(x)dx x f ę(x)dx = X A_kF(x_k), A_k

b

A_k = / <P_k (x) dx

a

Jeżeli |J^r(x) — (p(x)\ < e i xe<a; ó>, to

numeryczne