Harilik iteratsioonimeetod (0)

TALLINNA TEHNIKAÜLIKOOL
Nimi perenimi
 HARILIK ITERATSIOONIMEETOD
REFERAAT
Juhendaja : nimi
Tallinn 2016
 

Sisukord

Mis on iteratsioonimeetod? 3
Harilik iteratsioonimeetod 4
Meetodi realisatsioon 8
Näide 1) 8
Näide 2) 9
Allikad 11

Mis on iteratsioonimeetod?

Väga keerulist võrrandit õnnestub harva täpselt lahendada. Seega on vajalikud neil juhtudel ligikaudsed meetodid. Enamus võrrandif(x) =0 ligikaudsetest lahendamismeetoditest on nn iteratsioonimeetodid. Põhimõtteliselt võib iteratsioonimeetodi jagada
kaheks osaks:
1) leitakse alglähend x0;milleks on mingi otsitavale lahendile küllaltlähedal paiknev arv (mitmesammulise meetodi puhul läheb vaja mitutalglähendit).
2) täpsustatakse alglähendit nõutava täpsuseni.
Kõigi iteratsioonimeetodite põhiidee seisneb järgnevas: ülesandele leitakse mingi alglähend x1, mille abil moodustatakse lähendite jada x1; x2; x3; ...; xn; .... .
Teatud tingimustel koondub see jada ülesande täpseks lahendiks x*.
Iteratsioonimeetodeid on erinevaid, näiteks dihhotoomia meetod, harilik iteratsioonimeetod, Newtoni meetod ja modifitseeritud Newtoni meetod.
Järgnevalt vaatleme põhjalikumalt harilikku iteratsioonimeetodit.

Harilik iteratsioonimeetod

Uurime võrrandi
f (x) = 0 (1.24.1)
ligikaudset lahendamist. Esitame võrrandi (1.24.1) kujul
x = g (x) . (1.24.2)
Selleks on palju võimalusi, kusjuures üks lihtsamaid on valik
g (x) = x + cf (x), kus c ≠ 0
on mingi reaalne konstant. Olgu arv x0 võrrandi (1.24.1), seega ka võrrandi (1.24.2),
täpse lahendi x∗ mingi alglähend. Selle alglähendi (nn lähislahendi) x0 võime näiteks
saada skitseerides funktsiooni f (x) graafiku. Olgu
xn+1 = g (xn) (n ∈ N ∪). (1.24.3)
Algoritmiga (1.24.3) oleme määranud võrrandi (1.24.1) lahendi x* lä .
Teatud eeldustel funktsiooni g(x) koondub täpseks lahendiks x∗ , st
Kui x∗ on võrrandi (1.24.1) täpne lahend , siis
x* = g (x* ) . (1.24.4)
Seostest (1.24.3) ja (1.24.4) järeldub, et iga n ∈ N ∪ korral
xn+1 − x* = g(xn) − g (x*)
siis seoste (1.24.5) ja (1.24.6) põhjal saame
|xn+1 − x∗ | ≤ q |xn − x∗ | .
Seega
|xn − x∗ | ≤ q |xn−1 − x∗ | ≤ q2 |xn − x∗ | ≤ . . . ≤ qn |x0 − x∗ | ,
st kehtib hinnang
|xn − x∗ | ≤ qn |x0 − x∗ | . (1.24.7)
Kui q Algoritmil (1.24.3) põhinevat võrrandi (1.24.2) lahendamise meetodit nimetatakse harilikuks iteratsioonimeetodiks.
Teoreem :
Leidugu võrrandi (1) lahendit x* sisaldav vahemik (a, b), milles on täidetud võrratus (3). Olgu funktsioon g(x) selline, et ∀x ∈ (a, b) korral g(x) ∈ (a, b). Olgu x0 ∈ (a, b). Siis koondub hariliku iteratsioonimeetodiga arvutatud lähendite jada xn täpseks lahendiks x*. Lisaks kehtib veahinnang
| xn – x*| ≤ | x1 − x0 |. (4)
Tõestus:
Et x0 ∈ (a, b) ja g(x) ei vii vahemikust (a, b) välja, siis x1 = g(x0) ∈ (a, b), x2 = g(x1) ∈ (a, b), ...., xn = g(xn-1) ∈ (a, b). Et x* on võrrandi (1) täpne lahend , siis
x* = g(x*).
Lahutame seosest (2) viimase võrduse, saame
Xn – x* = g(xn-1) – g(x*).
Kasutame Langrange’i keskväärtusteoreemi:
(Punktide xn-1 ja x* vahel leidub punkt cn nii, et g(xn-1) – g(x*) = g’(cn)(xn-1 – x*).)
Seega
Xn – x* = g’(cn)(xn-1 – x*).
Teame, et xn-1, x* ∈ (a, b), järelikult ka cn ∈ (a, b). Meie eelduse põhjal |g’(cn)| ≤ q Järelikult
|xn – x*| = |g’(cn)(xn−1 – x*)| = |g’(cn)||(xn−1 – x*)| ≤ q|(xn−1 – x*)|.
Rakendame seda hinngangut korduvalt
|xn – x*| ≤ q|xn−1 – x*| ≤ q2|xn−2 – x*| ≤ . . . ≤ qn|x0 – x*|.
Näitasime, et
|xn – x*| ≤ qn|x0-x*|. (5)
Et q |xn – x*| → 0, kui n → ∞.
Koondumine xn → x* on näidatud .
Valem (5) ei sobi praktilistes arvutustes, sest paremal pool on tundmatu suurus x*. Tuletame praktilisema hinnangu.
|x0 – x*| = |x0 − x1 + x1 – x*| ≤ |x0 − x1| + |x1 – x*| ≤ |x0 − x1| + q|x0 – x*|.
Koondades selles võrratuses sarnased liikmed, saame
(1 − q)|x0 – x*| ≤ |x0 − x1|,
siit
|x0 – x*| ≤
|x1 − x0|.
Jagasime suurusega 1 – q (1 – q > 0, sest q Kasutades saadud hinnangud seoses (5) saimegi hinnangu (4).
Hinnangu (4) paremat poolt võib ka vaadelda, kui geomeetrilist jada a, aq, aq2, ..., kus a = =. Et q harilik iteratsioonimeetod koondub geomeetrilise progressioni kiirusega

Meetodi realisatsioon

Näide 1)

Vastavalt tõestatud teoreemile oleme leidnud koonduva hariliku iteratsioonimeetodi. Seega saame leida võrrandi x3 + 2x – 1 = 0 ligikaudse lahendi eeskirjaga xn = 0,5(1 – xn-13)
Ehk
X0 = 0,5
x1 = 0,5(1 – x03) = 0,5(1 – 0,53) = 0,4375
x2 = 0,5(1 – x13) ≈ 0,4581
x3 = 0,5(1 – x23) ≈ 0,4519
X10 ≈ x11 ≈ 0,4534.
Kontrolliks: 0,45343 + 2*0,4534 – 1 ≈ 6,14 * 10-6

Näide 2)

Lahendame võrrandi
2x – cos x = 0 (2.0)
täpsusega 10-5.
Skitseerime graafikule y = x ja y = cos x, millede lõikepunkti uurimisel saame ligikaudse x- teljega lõikepunkti võrrandile y = 2x – cos x.
Jooniselt on näha, et võrrandil (2.0) on vaid üks lahend ja alglähendiks sobib x0 = 0.5. Võrrrand on esitatav kujul
x = cos(x)/2
Saame rakendada algoritmi 1.24.3. Leiame
x1 = cos(0.5)/2 = 0.43879
x2 = cos(0.43879)/2 = 0.45263
x3 = cos(0.45263)/2 = 0.44965
x4 = cos(0.44965)/2 = 0.4503
x5 = cos(0.4503)/2 = 0.45016
x6 = cos(0. 45016)/2 = 0.45019
x7 = cos(0.45019)/2 = 0.45018
x8 = cos(0.45018)/2 = 0.45018
Seega saame, et x≈0.45018

Allikad

1) http://www.staff.ttu.ee/~kairik/rakmatloeng2_2012.pdf
2)Tammeraid I., “Matemaatiline analüüs I”, Tallinn 2001
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Alljärgnevad materjalid on juurde pandud, et allikate arvu suurendada, reaalselt on kasutatud vaid esimest ja teist
3)Võhandu L, Tamme E., Luht L., „Arvutusmeetodid I“, Tallinn „Valgus“, 1986
4) http://www.tlu.ee/~tonu/Arvmeet/arv2ja3.pdf
5) http://kodu.ut.ee/~mkolk243/2015/NM/2/NM-praktikum-2.pdf