Newtons modifiserte metode.

Vi lister opp ulempene med Newtons metode, som tar sikte på å eliminere dens ulike modifikasjoner:

vanskeligheten med å sette den innledende tilnærmingen som metoden konvergerer fra;

behovet for å beregne den jakobiske matrisen ved hver iterasjon, noe som kan kreve betydelige beregningskostnader;

behovet for å løse et system med lineære algebraiske ligninger ved hver iterasjon;

kravet om at Jacobi-matrisen skal være ikke-degenerert.

La oss vurdere modifikasjoner av Newtons metode, som til en viss grad eliminerer de oppførte manglene.

Newtons metode med en stykkevis konstant matrise.

For å redusere beregningskostnadene for iterasjoner, forblir Jacobi-matrisen i denne modifikasjonen konstant over flere trinn. Antall trinn m, hvor J er konstant, er spesifisert som en parameter i denne modifikasjonen, eller tidspunktet for omberegning av den jakobiske matrisen bestemmes av betingelsen

der, for eksempel (Jacobi-matrisen beregnes på nytt bare hvis denne betingelsen brytes).

Effektiviteten til metoden oppnås i dette tilfellet ikke bare ved å redusere antall beregninger av Jacobi-matrisen, men hovedsakelig på grunn av det faktum at på m iterasjoner av metoden, må man løse lineære systemer med samme matrise.

Newton-Raphson-metoden.

For å sikre konvergensen av metoden fra den valgte innledende tilnærmingen, brukes en modifikasjon kalt Newton-Raphson-metoden. beregning (k+ 1) tilnærmingen i denne modifikasjonen utføres i henhold til regelen

hvor er parameteren hvis verdi er på k iterasjonen velges fra betingelsen

Strategien for å velge en parameter i en iterasjon kan være som følger. Innledningsvis tas en prøveverdi eller, videre, denne verdien modifiseres til den formulerte betingelsen er oppfylt. Denne tilstanden kan kreve flere evalueringer av vektoren ved gjeldende iterasjon. Åpenbart, ved , faller Newton-Raphson-metoden sammen med Newton-metoden.

Videreføringsmetoder etter parameter.

Disse metodene gjør det mulig å sikre konvergensen av Newtons metode fra den valgte initiale tilnærmingen Essensen av metodene for fortsettelse med hensyn til en parameter er å erstatte opprinnelig oppgave sekvens av oppgaver, skiller hver påfølgende oppgave seg litt fra den forrige. Sekvensen er konstruert på en slik måte at det første systemet har en løsning, og siste system samsvarer med det opprinnelige problemet. Siden systemene er litt forskjellige, vil løsningen av det forrige problemet være en god innledende tilnærming for den neste. Ved å løse en slik sekvens av problemer ved Newtons metode, vil vi etter hvert få en løsning på det opprinnelige systemet. Vurder en metode for å konstruere den angitte sekvensen av oppgaver.

La når du løser systemet

den første gjetningen brukes. Vi erstatter den opprinnelige ligningen med en ligning med parameteren

som for har en løsning, og for sammenfaller med løsningen av det opprinnelige problemet, dvs.

Du kan velge funksjoner som

La oss dele segmentet etter poeng i intervaller. Vi får ønsket rekkefølge av systemer:

Newtons metode for dårlig betingede problemer.

Hvis Jacobi-matrisen er dårlig kondisjonert, er feilen ved å løse det lineære systemet

kan være betydelig på grunn av avrundingsfeil. Derfor, i

i tilfelle av dårlig betingede matriser, ved beregning av korreksjonsvektoren, systemet

med en numerisk parameter, hvor E-identitetsmatrise. For , det modifiserte systemet sammenfaller med lineært system Newtons standardmetode, når det er en tendens til enhet, har tilstandsnummeret til det modifiserte systemet også en tendens til enhet. Imidlertid forverres konvergenshastigheten til den tilsvarende metoden betydelig, siden for , metoden degenererer til metoden med enkle iterasjoner.

Erfaring viser at i studiet av ikke-kvadratiske funksjoner er Newtons metode lite pålitelig. Faktisk, hvis poenget X(0) er i betydelig avstand fra punktet X*, Newton-trinnet viser seg ofte å være for stort, noe som kan føre til manglende konvergens. Metoden kan ganske enkelt modifiseres for å redusere objektiv funksjon fra iterasjon til iterasjon og søk langs en rett linje, som i Cauchy-metoden. Rekkefølgen av iterasjoner er bygget i samsvar med formelen

x = x -α f(x)f(x).(3.56)

Valg α utføres på en slik måte at

f(x) → min;

dette garanterer oppfyllelsen av ulikheten

f(x) ≤ f(x).

En slik metode kalles modifiserte Newtons metode og i tilfeller der beregningen av de eksakte verdiene til de første og andre derivatene ikke er forbundet med betydelige vanskeligheter, viser det seg å være pålitelig og effektivt. Men når du bruker den modifiserte Newton-metoden, ved hver iterasjon, blir det nødvendig å konstruere og løse en lineær ligning som inneholder elementer av Hessen-matrisen f().

Marquardt-metoden

Metoden som vurderes er en kombinasjon av Cauchy- og Newton-metodene, som vellykket kombinerer de positive egenskapene til begge metodene. Men når du bruker Marquardt-metoden nødvendig informasjon om verdiene til de andre deriverte av objektivfunksjonen. Det ble bemerket ovenfor at gradienten indikerer retningen til den største lokale økningen i funksjonen, og bevegelse i motsatt retning av gradienten fra punktet X(0) plassert i betydelig avstand fra minimumspunktet X*, fører vanligvis til en betydelig reduksjon i den objektive funksjonen. På den annen side er retningene for effektivt søk i nærheten av minimumspunktet bestemt av Newtons metode. enkel idéå kombinere Cauchy- og Newton-metodene var grunnlaget for algoritmen utviklet av Marquardt i 1963. I samsvar med denne metoden bestemmes søkeretningen av likheten

s(x(k)) = – [H(k) + λ (k) Jeg] -1 f (x(k)). (3,57)

I dette tilfellet, i formel (3.42) bør man sette α (k) = +1, siden parameteren λ tillater ikke bare å endre retningen på søket, men også justere trinnlengden. Symbol Jeg her er identitetsmatrisen betegnet, dvs. matrisen, hvis alle elementer er lik null, bortsett fra de diagonale elementene lik +1. På det første stadiet søkeparameter λ (0) er tildelt veldig viktig(f.eks. 10 4), så

[H(0) +λ(0) Jeg] -1 = [λ(0) Jeg] -1 = JEG. (3.58)

På denne måten, store verdierλ (0) tilsvarer søkeretningen s( x (0)) → f (x(0)) Fra formel (3.57) kan vi konkludere at med synkende λ ned til null s(x) endres fra retningen motsatt til gradienten til retningen bestemt av Newtons metode. Hvis det etter det første trinnet oppnås et punkt med en mindre verdi av objektivfunksjonen (dvs. f(X (1)) < f(x(0))), bør man velge λ (1)< λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β >1 og implementer forrige trinn på nytt. Nedenfor er trinnene til algoritmen.

Marquardts algoritme

Trinn 1. Sett X(0) - innledende tilnærming til X*; M- det maksimale (tillatte) antall iterasjoner; ε er konvergensparameteren.

Trinn 2. Sett k= 0, λ (0) = 104.

Trinn 3. Beregn komponentene f (x(k)).

Trinn 4. Holder ulikheten?

|| f (x(k))||< ε?

Ja: gå til trinn 11.

Trinn 5. Holder ulikheten? k ≥ M?

Ja: gå til trinn 11.

Nei: gå til neste trinn.

Trinn 6. Beregn s(x(k)) = – [H(k) + λ (k) Jeg] -1 f (x(k)).

Trinn 7. Sett x = xs(x).

Trinn 8. Holder ulikheten? f(x) < f(x)?

Ja: gå til trinn 9.

Nei: Gå til trinn 10.

Trinn 9. Sett λ (k +1) = ½ λ (k) og k = k+ 1. Gå til trinn 3.

Trinn 10. Sett λ (k) = 2λ (k) . Gå til trinn 6.

Trinn 11 Skriv ut resultater og stopp.

Marquardt-metoden er preget av relativ enkelhet, egenskapen til å redusere objektivfunksjonen i overgangen fra iterasjon til iterasjon, en høy konvergenshastighet i nærheten av minimumspunktet x* , og også ved fravær av en søkeprosedyre langs en rett linje. Den største ulempen med metoden er behovet for å beregne H(k) og påfølgende løsning av systemet lineære ligninger tilsvarende (3,57). Denne metoden er mye brukt for å løse problemer der f(x) skrives som summen av kvadrater 1) , dvs.

f(x) = f(x) + f(x) +…+ f(x). (3.59)

Det var dette problemet Marquardt vurderte. Powell og Bard, basert på beregningseksperimenter, viste at Marquardt-metoden er forskjellig høy effektivitet når du løser problemer av denne typen.

Newtons metode og sekantmetoden

Newtons metode i tilfelle av en enkel reell rot har formen

x k+1 = x k - ― ――, k = 1,2,…. (8.6)

f′(xk)

når det gjelder multiplisitetsroten r

x k +1 - x k

f ′(x k) ― ――― + f(x k) = 0 .

Feilanslaget er som følger:

|x k - x *| £ q |x 0 - x *|, k = 1,2,….

M p+1 |x 0 - x * |

q = ―――――< 1.

m p p(p + 1)

Du kan bruke feilestimatet som i den enkle iterasjonsmetoden, gitt at Newtons metode

sx) = x – p ――

x k+1 = x k - ― ――, k = 0, 1, ….

f′(x0)

brukes når du vil unngå gjentatt beregning av den deriverte ¦¢(xk).

I Newtons metode kreves det å beregne den deriverte av en funksjon, noe som ikke alltid er praktisk. Du kan erstatte den deriverte med den første delte forskjellen funnet over de to siste iterasjonene. Da får vi i stedet for Newtons metode (8.6). sekantmetode

(x k – x k -1)f(x k)

x k+1 = x k - ― ― ― ― ――

f(x k) – f(x k-1)

For å starte prosessen må du kjenne til verdiene x 0 og x 1.

OPPGAVER FOR LABORATORIEARBEID.

1. Skill reelle røtter analytisk eller grafisk.

2. Avgrens røttene ved å dele segmentet i to (hvis mulig) med en nøyaktighet på 0,1.

3. Avgrens røttene etter en gitt metode med en gitt nøyaktighet.

For Newtons metode og den enkle iterasjonsmetoden er antall iterasjoner som er nødvendig for å oppnå en gitt nøyaktighet valgt på forhånd ved å estimere feilen manuelt. For andre metoder stopper iterasjoner etter forskjellen på to påfølgende tilnærminger blir mindre enn den angitte nøyaktigheten.

4. Sjekk resultatene ved å erstatte de funnet verdiene i ligningen.

ALTERNATIVER

1. Finn alle røttene til ligningen

1000000 x 4 - 3000 x 3 + 1000002 x 2 - 3000 x + 2 = 0

med en nøyaktighet på 0,0001 ved metoden a) Newton b) sekant.

2. Finn alle røttene til ligningen

x 4 - 10001,01 x 3 -9800,01 x 2 - 999901 x + 10000 = 0

med en nøyaktighet på 0,001 a) Newtons metode b) Modifisert Newtons metode.

3. Finn alle røttene til ligningen

på et segment med en nøyaktighet på 0,001 ved Newtons metode.

4. Finn alle røttene til ligningen

5. Finn roten til ligningen

x 4 - 20 x 3 + 101 x 2 - 20 x + 1 = 0

på intervallet [-1,1] med en nøyaktighet på 0,0001 ved Newtons metode med parametere

gitt nøyaktighet.

6. Finn roten til ligningen

7. Finn alle røttene til ligningen

x5 - 3x2 + 1 = 0

ved den parabolske metoden med en nøyaktighet på 0,0005.

8. Finn de virkelige røttene til ligningen

9. Finn ut hvilken av røttene 0, 1, -1 i ligningen

Newtons metode konvergerer hvis vi tar utgangspunkt i en vilkårlig initial tilnærming. Hvilke innledende tilnærminger gir divergensen til metoden?

10. Finn alle røttene til ligningen

x 3 + 3 x 2 - 1 = 0

enkel iterasjonsmetode med en nøyaktighet på 0,0005.

11. Finn alle røttene til ligningen

x 4 - 10000,01 x 3 +101 x 2 - 10000,01 x + 100 = 0

nøyaktig til 0,001 a) Newtons metode b) modifisert Newtons metode.

12. Finn roten til ligningen

arccos (x/2) = x 2

på intervallet a) ved Newtons metode b) ved den modifiserte Newtons metode.

13. Finn alle røttene til ligningen

x 4 - 0,015x 3 + 0,3x 2 + x - 1 = 0

14. Finn roten til ligningen

x 3 - sin (2x) \u003d 1

ved den parabolske metoden med en nøyaktighet på 0,001.

15. Finn alle røttene til ligningen

x 3 - 1777 x 2 + 777 = 0

på intervallet [-1,1] ved den parabolske metoden med en nøyaktighet på 0,0001

16. Finn alle røttene til en ligning

5555x 4 - 555x 3 - 55x 2 - 5x = 0

med en nøyaktighet på 0,00001 ved metoden a) Newton b) sekant.

17. Finn roten til ligningen

arctan(7x) = 0,2

på intervallet [-1,1] a) Newtons metode b) modifiserte Newtons metode.

atten . Finn roten til ligningen

sin (x 4) = 1 - 2x

ved den parabolske metoden med en nøyaktighet på 0,0001.

19. Finn roten til ligningen

med en nøyaktighet på 0,001 ved Newtons metode. Utfør iterasjoner til forskjellen mellom tilstøtende iterasjoner blir mindre enn den angitte nøyaktigheten. Sammenligne nødvendige mengder iterasjoner.

20. Finn alle røttene til en ligning

x 3 - 45x 2 + 43 = 0

på segmentet [-2,1] a) modifisert Newtons metode b) sekantmetode.

21. Finn roten til ligningen

arcsin(x) + e x = 2

ved metoden med enkel iterasjon med en nøyaktighet på 0,001 ved å gjøre et foreløpig estimat av feilen.

22. Finn alle røttene til en ligning

54x4 + x2 - 0,0000001 =0

med en nøyaktighet på 0,00001 ved metoden a) Newton b) sekant.

23. Finn alle røttene til en ligning

tg (x / 3) - x 3 \u003d 0

ved den parabolske metoden med en nøyaktighet på 0,001.

24. Finn alle røttene til en ligning

12x4 + 11x3 -10x2 -999 = 0

på segmentet [-3,5,3] med en nøyaktighet på 0,0001 ved Newton-metoden med parametere

p=1 og p=2. Sammenlign antall iterasjoner som trengs for å oppnå

gitt nøyaktighet.

25. Finn roten til ligningen

med en nøyaktighet på 0,0001 ved Newton-metoden og den modifiserte Newton-metoden. Utfør iterasjoner til forskjellen mellom tilstøtende iterasjoner blir mindre enn den angitte nøyaktigheten. Sammenlign det nødvendige antallet iterasjoner.

SVAR:1) 0,0100; 0,0200 2) 0,688; 10000 3) 0,107; 0,155; 0,361 4) –1,32; 0; 1,32 5) 0,0917; 0,1125 6) 0 7) –0,5611; 0,5992; 1,348 8) –0,637; 1,41 9) –1; 0; 1 10) -2,879; -0,6527; 0,5321 11) 0,231; 10000 12) 1,01817183 13) –1,1468; 0,66935; 1 14) 1,191 15) -0,6611; 0,6614 16) –0,09811;0,19695 17) 0,028959 18) 0,4746 19) 0,987 20) –0,9672; 0,9884; 44,98 21) 0,4369 22) +/- 0,0003 23) +/- 0,581; 0 24) -3,36; 2,875 25) 1,2784.

Den modifiserte Newton-metoden er basert på Newtons metode. Hvis den deriverte endrer seg litt på segmentet, kan vi anta.

Herfra, for roten av ligningen, får vi suksessive tilnærminger

N=0,1,2... (1,16)

Geometrisk betyr denne metoden at vi erstatter tangentene i punkter med linjer parallelle med tangenten til kurven i et fast punkt.

Denne metoden lar deg nekte gjentatt beregning av derivatet på poeng. Den modifiserte Newton-metoden brukes til å løse ligninger der beregningen av den deriverte er arbeidskrevende og relativt langsiktig. I andre tilfeller er det bedre å bruke standard Newton-metoden.

Begrensningene for funksjonen og den første tilnærmingen for de modifiserte og standard Newton-metodene er de samme. Algoritmen til begge metodene er nesten den samme.

Den modifiserte Newton-metoden har lineær konvergens

Metoden garanterer ingen divisjon med null hvis .

Eksempel. Ligningen.

Bruk Newtons metode med en parameter, fordi roten har multiplisitet p=2. Vi tar den første tilnærmingen og får. Rot funnet.

Eksempel. Ligningen.

Roten er isolert på et kutt. Eps-feilen er 0,000001

Newtons metode konvergerer i 5 iterasjoner, modifisert Newtons metode i 19 iterasjoner, metode halv divisjon for 22 iterasjoner. Konvergensen av iterasjonsmetoden avhenger av valget av parameteren. Med konvergens oppnås i 24 iterasjoner, konvergens i 11 iterasjoner, konvergens i 6 iterasjoner, konvergens i 25 iterasjoner.

Sekantmetoden

Sekantmetoden er hentet fra Newtons metode ved å erstatte den delte forskjellen

beregnet ved kjente tilnærminger og.

Følgelig oppnås følgende formel for sekanteringsmetoden

. (1.18)

Denne metoden er to-trinns (fordi du må kjenne til de to foregående trinnene for å utføre et nytt trinn). I dette skiller det seg fra alle tidligere gitte metoder - ett trinn.

For sekantmetoden velges den første tilnærmingen først. Videre, ved å bruke formelen til en annen metode eller på en annen måte, beregnes den andre innledende tilnærmingen. Og først da, for å beregne påfølgende tilnærminger, brukes formelen til sekantmetoden.

Integrasjon av funksjoner Redegjørelse av problemstillingen

La en kontinuerlig funksjon gis på et intervall. La oss konstruere en partisjon av segmentet med et punkt og delsegmenter:

Lengden på segmentene er .

La oss kalle integralsummen

Det bestemte integralet til en funksjon på et segment kalles

Klasser av integrerbare funksjoner og deres egenskaper vurderes i teorien om matematisk analyse og diskuteres ikke her. Vi vil anta at funksjonen vår er integrerbar på intervallet.

Hvordan kan integralen beregnes i praksis? For dette brukes vanligvis Newton-Leibniz-formelen:

hvor P(x) - antiderivat av funksjon F(x) , dvs..

Newton-Leibniz-formelen spiller en viktig rolle i matematisk analyse. Men kan det brukes når du løser et problem på en datamaskin? Det er mulig, men ikke alltid (siden antiderivatet ikke alltid eksisterer).

Er det praktisk å bruke det i programmering? Nei, du må kjenne det primitive. I tillegg, hvis funksjonen er gitt av en graf eller tabell, kan integralet fra den ikke beregnes med denne formelen.

Dette lar oss konkludere med at Newton-Leibniz-formelen ikke gir en generell, universell metode for å finne en bestemt integral av en vilkårlig funksjon, og det anbefales ikke å bruke den i profesjonelle dataprogrammer. Newton-Leibniz-formelen brukes kun til å teste nyutviklede programmer der andre metoder for omtrentlig integrering av funksjoner er implementert.

Nedenfor vil universelle beregningsalgoritmer for å løse problemet med numerisk integrasjon bli presentert. Slike metoder gjør det mulig å beregne integraler direkte fra verdiene til integranden og avhenger ikke av måten den er spesifisert på.

De tilsvarende formlene kalles numeriske integrasjonsformler eller kvadraturformler 5 .

Partisjoneringstrinnet i dette tilfellet beregnes av formelen.