Lagrangen interpolaatiopolynomi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25.11.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Lagrangen interpolaatiopolynomi on vähimmäisasteinen polynomi, joka saa tietyt arvot tietyssä pistejoukossa, eli ratkaisee interpolointiongelman .

Määritelmä

Olkoon lukupari, jossa kaikki ovat erilaisia. Vaaditaan korkeintaan astepolynomi , jolle . $n+1$ $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$ $x_{j}$ $L(x)$ $n$ ${\displaystyle L(x_{j})=y_{j))$

Yleinen tapaus

J. L. Lagrange ehdotti seuraavaa menetelmää tällaisten polynomien laskemiseksi:

L(x)=\sum _{i=0}^{n}y_{i}l_{i}(x),

jossa peruspolynomit määritetään kaavalla $l_{i}$

l_{i}(x)=\prod _{j=0,j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}} }={\frac {x-x_{0}}{x_{i}-x_{0}}}\cdots {\frac {x-x_{i-1}}{x_{i}-x_{i- 1}}}\cdot {\frac {x-x_{i+1}}{x_{i}-x_{i+1}}}\cdots {\frac {x-x_{n}}{x_{i }-x_{n}}}

Jokaisella polynomilla on aste ja $i=0,\ldots ,n$ $l_{i}$ $n$

l_{i}(x_{j})=\left\{{\begin{array}{rl}0,&j\neq i,\\1,&j=i.\end{array}}\right .

Tämä tarkoittaa, että , joka on polynomien lineaarinen yhdistelmä , on enintään aste ja . $L(x)$ $l_{i}(x)$ $n$ $L(x_{i})=y_{i}$

Tasavälisten interpolointisolmujen tapaus

Olkoot interpolointisolmut yhtä kaukana toisistaan, eli ne ilmaistaan aloituspisteen ja jonkin kiinteän positiivisen arvon muodossa seuraavasti: $x_{j}$ $x_{0}$ $h$

x_{j}=x_{0}+jh.

Tästä seuraa siis

x_{j}-x_{i}=(ji)h.

Korvaamalla nämä lausekkeet peruspolynomin kaavaan ja poistamalla tulon merkit osoittajasta ja nimittäjästä saadaan $h$

l_{j}(x)={\prod _{i=0,\,i\neq j}^{n}{(x-x_{i}) \over (x_{j}-x_{ i})}}={\prod \limits _{i=0,\,i\neq j}^{n}(x-x_{0}-ih) \over h^{n}\prod \limits _ {i=0,\,i\neq j}^{n}(ji)}

Nyt voimme ottaa käyttöön muuttujan muutoksen

y={{x-x_{0}} \over h}

ja saada lauseke peruspolynomeille muodossa , joka on rakennettu käyttämällä vain kokonaislukuaritmetiikkaa : $y$

l_{j}(x)=l_{j}(x_{0}+yh)=(-1)^{nj}C_{n}^{j}{\dfrac {y(y-1) \ldots (yn)}{(yi)n!}}.

Näitä suureita kutsutaan Lagrange-kertoimiksi. Ne eivät ole riippuvaisia tai siitä, ja siksi ne voidaan laskea etukäteen ja kirjoittaa taulukoiden muodossa. Tämän lähestymistavan haittana on osoittajan ja nimittäjän monimutkaisuus, mikä edellyttää pitkän aritmeettisen menetelmän käyttöä . $y_{0},\ldots ,y_{n}$ $h$

Loput

Jos katsomme lukuja jonkin funktion arvoina solmuissa , niin funktion polynomin interpoloinnin virhe on yhtä suuri kuin $y_{0},\ldots ,y_{n}$ $f$ ${\displaystyle x_{0},\ldots ,x_{n))$ $f$ $L$

f(x)-L(x)={\dfrac {f^{(n+1)}(\xi )}{(n+1)!}}(x-x_{0})\ldots (x-x_{n}),

jossa on jokin keskipiste numeroiden pienimmän ja suurimman välillä . Olettaen , että voi kirjoittaa $\xi$ ${\displaystyle x_{0},\ldots ,x_{n))$ $M_{n+1}=\sup _{x\in [x_{0},x_{n}]}|f^{(n+1)}(x)|$

|f(x)-L(x)|\leqslant {\dfrac {M_{n+1}}{(n+1)!}}|(x-x_{0})\ldots (x- x_{n})|.

Ainutlaatuisuus

On olemassa yksi polynomi, jonka aste ei ylitä ja joka ottaa annetut arvot tietyssä pisteessä. $n$ $n+1$

Todiste

Oletetaan, että on olemassa enintään kaksi erilaista astepolynomia , joille on totta, että lukupareille, joissa kaikki ovat erilaisia, Tarkastellaan polynomia . Korvaamalla sen ( ), saamme sen . Näin ollen polynomilla on juuret ja ne ovat kaikki erilaisia. Siksi , koska korkeintaan nollasta poikkeavalla astepolynomilla on enintään juuret. Siksi ,. ■ ■ $P(x)$ $Q(x)$ $n$ $n+1$ $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$ $x_{j}$ $P(x_{j})=Q(x_{j})=y_{j}.$ $L(x)=P(x)-Q(x)$ $x_{j}$ $0\leq j\leq n$ $L(x_{j})=P(x_{j})-Q(x_{j})=y_{j}-y_{j}=0$ $L(x)$ $n+1$ $L(x)\equiv 0$ $n$ $n$ $P(x)=Q(x)$

Tämä väite on yleistys siitä tosiasiasta, että minkä tahansa kahden pisteen läpi kulkee vain yksi viiva.

Lineaarialgebran näkökulmasta

Interpolaatiopolynomin ainutlaatuisuutta voidaan tarkastella myös SLAE :n näkökulmasta . Tarkastellaan yhtälöjärjestelmää . Se on nimenomaisesti kirjoitettu nimellä ${\displaystyle P(x_{0})=y_{0},P(x_{1})=y_{1},\dots ,P(x_{n})=y_{n))$

{\begin{cases}a_{0}+a_{1}x_{0}+a_{2}x_{0}^{2}+\pisteet +a_{n}x_{0}^{n }=y_{0},\\a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+\pisteet +a_{n}x_{1}^{n }=y_{1},\\\pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä \pisteitä ,\\a_{0}+a_{1}x_{n}+ a_{2}x_{n}^{2}+\pisteet +a_{n}x_{n}^{n}=y_{n}\\\end{cases}}

Se voidaan kirjoittaa uudelleen yhtälöjärjestelmäksi , jolla on tuntematon vektori : $Xa=y$ $a=(a_{0},a_{1},\dots ,a_{n})$

{\begin{bmatrix}1&x_{0}&x_{0}^{2}&\pisteet &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\pisteet &x_ {1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\ \end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\ \y_{1}\\\vdots \\y_{n}\end{bmatrix}}

Tällaisen järjestelmän matriisi on Vandermonde -matriisi ja sen determinantti on . Vastaavasti, jos kaikki pisteet ovat erilaisia, matriisi on ei-degeneroitunut ja järjestelmällä on ainutlaatuinen ratkaisu. $X$ $\prod \limits _{i<j}(x_{i}-x_{j})$ ${\displaystyle x_{0},x_{1},\dots ,x_{n))$

Kiinan jäännöslauseen suhteen

Bezoutin lauseen mukaan jaon jäännös on . Siten koko järjestelmä voidaan nähdä vertailujärjestelmänä: $P(x)$ $(xa)$ $P(a)$

{\begin{cases}P(x)\equiv y_{0}{\pmod {x-x_{0}}},\\P(x)\equiv y_{1}{\pmod {x- x_{1}}},\\\pisteet ,\\P(x)\equiv y_{n}{\pmod {x-x_{n}}},\\\end{cases}}

Kiinan jäännöslauseen mukaan tällaisella järjestelmällä on ainutlaatuinen ratkaisu modulo , eli annettu järjestelmä määrittää yksiselitteisesti korkeintaan astepolynomin . Tällainen polynomin esitys jäännösjoukkojen muodossa monomimoduulien yli on samanlainen kuin luvun esitys jäännösten muodossa jakamisesta yksinkertaisiin moduuleihin jäännösluokkien järjestelmässä . Tässä tapauksessa Lagrangen polynomin eksplisiittinen kaava voidaan saada myös kiinalaisen lauseen kaavojen mukaisesti : , missä ja . ${\näyttötyyli (x-x_{0})(x-x_{1})\pisteet (x-x_{n})}$ $n$ ${\textstyle P(x)=\sum \limits _{i=0}^{n}y_{i}M_{i}M_{i}^{-1))$ $M_{i}=\prod \limits _{j\neq i}(x-x_{j})$ $M_{i}^{-1}=\prod \limits _{j\neq i}(x-x_{j})^{-1}{\pmod {x-x_{i))}= \prod \limits _{j\neq i}(x_{i}-x_{j})^{-1}$

Esimerkki

Etsitään interpolointikaava seuraaville arvoille: $f(x)=\mathop {\mathrm {tg} } \nolimits (x)$

{\begin{aligned}x_{0}&=-1,5&&&&&f(x_{0})&=-14.1014\\x_{1}&=-0,75&&&&&f(x_{1})&=- 0,931596\ \x_{2}&=0&&&&&f(x_{2})&=0\\x_{3}&=0,75&&&&&f(x_{3})&=0,931596\\x_{4}&= 1,5&&&&&f(x_{4) })&=14,1014.\end{aligned}}

l_{0}(x)={x-x_{1} \over x_{0}-x_{1}}\cdot {x-x_{2} \over x_{0}-x_{2} }\cdot {x-x_{3} \over x_{0}-x_{3}}\cdot {x-x_{4} \over x_{0}-x_{4}}={1 \over 243} x(2x-3)(4x-3)(4x+3)

l_{1}(x)={x-x_{0} \over x_{1}-x_{0}}\cdot {x-x_{2} \over x_{1}-x_{2} }\cpiste {x-x_{3} \over x_{1}-x_{3}}\cdot {x-x_{4} \over x_{1}-x_{4}}={}-{8 \ yli 243}x(2x-3)(2x+3)(4x-3)

l_{2}(x)={x-x_{0} \over x_{2}-x_{0}}\cdot {x-x_{1} \over x_{2}-x_{1} }\cdot {x-x_{3} \over x_{2}-x_{3}}\cdot {x-x_{4} \over x_{2}-x_{4}}={3 \over 243} (2x+3)(4x+3)(4x-3)(2x-3)

l_{3}(x)={x-x_{0} \over x_{3}-x_{0}}\cdot {x-x_{1} \over x_{3}-x_{1} }\cdot {x-x_{2} \over x_{3}-x_{2}}\cdot {x-x_{4} \over x_{3}-x_{4}}=-{8 \over 243 }x(2x-3)(2x+3)(4x+3)

l_{4}(x)={x-x_{0} \over x_{4}-x_{0}}\cdot {x-x_{1} \over x_{4}-x_{1} }\cdot {x-x_{2} \over x_{4}-x_{2}}\cdot {x-x_{3} \over x_{4}-x_{3}}={1 \over 243} x(2x+3)(4x-3)(4x+3).

Saada

{\begin{aligned}L(x)&={1 \over 243}{\Big (}f(x_{0})x(2x-3)(4x-3)(4x+3)\ \&{}\qquad {}-8f(x_{1})x(2x-3)(2x+3)(4x-3)\\&{}\qquad {}+3f(x_{2})( 2x+3)(4x+3)(4x-3)(2x-3)\\&{}\qquad {}-8f(x_{3})x(2x-3)(2x+3)(4x+ 3) )\\&{}\qquad {}+f(x_{4})x(2x+3)(4x-3)(4x+3){\Big )}\\&=4,834848x^{3 }- 1,477474x.\end{aligned}}

Sovellukset

Numeerinen integrointi

Olkoon funktion arvot tiedossa joissakin kohdissa. Sitten voimme interpoloida tämän funktion Lagrange-menetelmällä: $f(x)$ $y_{i}=f(x_{i})$

f(x)\approx \sum _{i=0}^{n}f(x_{i})l_{i}(x).

Tuloksena olevaa lauseketta voidaan käyttää approksimoimaan funktion määrätyn integraalin laskenta : $f$

\int \limits _{a}^{b}f(x)dx\approx \sum _{{i=0}}^{n}f(x_{i})\int \limits _{a}^{ b}l_{i}(x)dx

Integraalien arvot eivät riipu ja ne voidaan laskea etukäteen käyttämällä sekvenssiä . $l_{i}$ $f(x)$ $x_{j}$

Kirjallisuus

Berezin, I. S. , Zhidkov N. P. Laskennalliset menetelmät. Osa I. - 2. painos, stereotyyppinen - M .: Fizmatlit . 1962.

Linkit

M. A. Tynkevich. Luku 7.6.1. Lagrangen interpolaatiopolynomi // Numeeriset analyysimenetelmät . - Kemerovo, 2002. - ISBN 5-89070-042-1 . (linkki ei saatavilla)
A. G. Khovansky. Lagrangen polynomit ja niiden sovellukset . Video luento. VI kesäkoulu "Moderni matematiikka ", Dubna, 2006.