Katere ničle najde algoritem bisekcija?

Katere ničle najde algoritem bisekcija?

Avtor: Sabina Oražem

Besedilo naloge

Denimo, da imamo funkcijo za katero je in ima na intervalu različnih enostavnih ničel. Statistično ocenite verjetnost, da metoda bisekcije poišče -to ničlo, .

Teorija

Naj bo zvezna funkcija na zaprtem intervalu , tako da . Potem ima vsaj eno ničlo na intervalu (a,b). Algoritem bisekcije generira zaporedja intervalov , kjer ležijo ničle funkcije . Naj bo in definirajmo . Ko je , je algoritma konec. Če je in , potem naj velja , kar pomeni, da z iskanjem ničle nadaljujemo na levi polovici prvotnega intervala. V primeru, ko je in , potem naj velja , kar pomeni, da z iskanjem ničle nadaljujemo na desni polovici prvotnega intervala. Ker velja , algoritem bisekcije zagotovo konvergira proti eni izmed ničel funkcije f na intervalu .

Algoritem bisekcije v MatLabu

(http://www2.nauk.si/files/576/algoritemML_1.png)
Koda algoritma bisekcije v MatLab-u

Nekaj rešitev

Poiščimo ničlo lihe funkcije 'sin(x)' na intervalu [a=-18.5, b=18.5]. Ker je (a+b)/2 = 0 in f(0) = 0, bo algoritem bisekcije našel ničlo točno na sredini danega intervala.

(http://www2.nauk.si/files/576/sin1_0.png)
Klic funkcije
(http://www2.nauk.si/files/576/sinGraf1.png)
Graf funkcije 'sin(x)' in z algoritmom bisekcije najdena ničla

Nekaj rešitev

Poiščimo ničlo lihe funkcije 'cos(x)' na intervalu [a=-18.5, b=17].

(http://www2.nauk.si/files/576/cos1.png)
Klic funkcije
(http://www2.nauk.si/files/576/cosGraf_0.png)
Graf funkcije 'cos(x)' in z algoritmom bisekcije najden približek ničle

Teorija

Če ima funkcija več kot le eno ničlo na intervalu , se lahko povprašamo katero ničlo funkcije algoritem pravzaprav najde. Če ima funkcija različnih in preprostih ničel na intervalu in , potem algoritem bisekcije najde ničlo s sodo zaporedno številko z verjetnostjo nič.

Naj predstavlja množico zveznih funkcij, ki zadoščajo pogoju in imajo natanko različnih in preprostih ničel na intervalu . Naj bodo ničle funkcije določene . Predvidevamo, da so položaji ničel neodvisni in naključno enakomerno porazdeljeni na intervalu. Naj bo in . Naj označuje verjetnost, da algoritem bisekcije konvergira proti ničli funkcije . Naj označuje verjetnost, da

za .

Če je sod, potem ni izpoljen pogoj . Če je lih, je za vse sode , saj na vsakem koraku, algoritem bisekcije zavrže en podinterval dolžine , ki vsebuje sodo število ničel. Zato ob sodem , bo ničla najdena le, če bo na neki točki bisekcije veljalo .

IZREK:

Za lihe :

Algoritem za iskanje verjetnosti

za prvi primer vzemimo funkcijo . Funkcija je zvezna in definirajmo jo na intervalu , kjer je naključno izbran iz intervala in naključno izbran z intervala . Na tem intervalu ima funkcija vedno ničel.

Na primeru bi radi preverili ali trditev o najdenih ničlah z algoritmom bisekcije velja (opisano na prejšnji prosojnici).

Na spodnji sliki je prikazana funkcija na intervalu . Opazimo lahko, da ima funkcija na tem intervalu točno 11 ničel, ki so enakomerno razporejene na mestih , , , , , , , , , , .

(http://www2.nauk.si/files/576/sinGraf.png)
Klic funkcije

Po trditvi (prejšnja prosojnica), naj metoda bisekcije ne bi nikoli našla ničel s sodim indeksom, torej ničel , , , , . Ničel z sodim indeksom pa naj bi bile najdene z verjetnostjo

.

Algoritem za iskanje verjetnosti

(http://www2.nauk.si/files/576/verSinFun_0.png)
Algoritem za iskanje 1000 ničel funkcije sin(x)

Algoritem za iskanje verjetnosti

Funkcija opisana na prejšnjih prosojnicah vrača vektor dolžine 11. V vektorju hranimo seštevek vseh najdenih ničel, pri 1000 poskusih.

(http://www2.nauk.si/files/576/verSin.png)
Vektor seštevka najdenih ničel

Kot vidimo sodih ničel metoda bisekcije ni našla. Na sodih mestih vektorja so vrednosti 0.

Seštevek vseh povprečij najdenih ničel je enak 1. Na intervalu je 6 lihih ničel, torej skupno povprečje je , kar je enako .

Literatura

  • Bisekcija, Fundacija Wiki, http://sl.wikipedia.org/wiki/Bisekcija_(numeri%C4%8Dna_metoda), 9.8.2013
  • Bisekcija, studentski.net, http://studentski.net/gradiva/ulj/fel/el1/numericne-metode.html?r=ulj_fel_el1_num_sno_primeri_programov_01.pdf, 9.8.2013
  • Mathematical Modelling: Classroom Notes in Applied Mathematics, SIAM, Philadelphia, 1987, str. 186{187
0%
0%