Algorytm aproksymujący podane na wejście punkty metodą najmniejszych kwadratów

Stronę tą wyświetlono już: 684 razy

Opis matematyczny aproksymacji metodą najmniejszych kwadratów.

Niechaj istnieje taki zbiór punktów P1, P2, ..., Pm, dla których szukana jest funkcja w postaci wielomianu n-tego stopnia, gdzie nm-1. Punkty P1, P2, ..., Pm można zapisać w następującej postaci:

begin{matrix}P_1.x = x_1 & P_1.y=f(x_1)\ P_2.x = x_2 & P_2.y=f(x_2)\ vdots & vdots\ P_m.x = x_m & P_m.y=f(x_m)end{matrix} [1]

sam zaś wielomian funkcji aproksymującej zadane punkty, będzie wyglądał w następujący sposób:

f_{apr}(x)=a_0cdot x^0+a_1cdot x^1+hdots+a_ncdot x^n [2]

co z kolei można w prostszy sposób zapisać:

f_{apr}(x)=sum_{i=0}^{n}a_icdot x^i [3]

Zaprawdę powiadam wam, że można wyznaczyć współczynniki a0, a1, ..., an wielomianu fapr(x) układając następującą macierz:

begin{bmatrix}w_{0,0} & w_{0,1} & hdots & w_{0, n} & w_{0, n+1}\ w_{1,0} & w_{1,1} & hdots & w_{1, n} & w_{1, n+1} \ vdots & vdots & ddots & vdots & vdots \ w_{n, 0} & w_{n, 1} & dots  & w_{n, n} & w_{n, n+1} 
end{bmatrix} [4]

gdzie współczynniki kolumn od 0 do n przyjmują wartości według następującego wzoru:

w_{i, j}=sum_{k=1}^{m}{x_k}^{i+j} [5]

dla ostatniej kolumny zaś, wartości współczynników obliczyć z wzoru:

w_{i, n+1}=sum_{k=1}^{m}{x_k}^{i}cdot f(x_k) [6]

Po wyliczeniu współczynników macierzy, należy niezwłocznie przejść do jej rozwiązania np. metodą Gaussa lub metodą Gaussa-Jordana.

Przykład rozwiązania

Niechaj podane będą następujące punkty: {1; 6}; {2; 8}; {4; 4}; {6; 2}; {8; 0}; {10; 2}. Wyznaczyć wielomian 2-giego stopnia aproksymujący te punkty.

Nie będzie wielkim rozwiązaniem tajemnicy, gdy stwierdzę, że konieczne jest utworzenie macierzy o rozmiarach n×n+1. Dla świętego spokoju rozpiszę tą macierz poniżej:

begin{bmatrix}w_{0,0} & w_{0,1} & w_{0,2} & w_{0,3}\ w_{1,0} & w_{1,1} & w_{1,2} & w_{1,3}\ w_{2,0} & w_{2,1} & w_{2,2} & w_{2,3}end{bmatrix} [7]

Wyznaczenie współczynników o indeksach kolumn od 0 do 2 (czyli do n):

w_{0,0}=sum_{k=1}^{m}{x_k}^{0+0}=6 [8]
w_{0,1}=sum_{k=1}^{m}{x_k}^{0+1}=1+2+4+6+8+10=31 [9]
w_{0,2}=sum_{k=1}^{m}{x_k}^{0+2}=1^2+2^2+4^2+6^2+8^2+10^2=221 [10]
w_{1,0}=sum_{k=1}^{m}{x_k}^{1+0}=w_{0,1}=31 [11]
w_{1,1}=sum_{k=1}^{m}{x_k}^{1+1}=1^2+2^2+4^2+6^2+8^2+10^2=221 [12]
w_{1,2}=sum_{k=1}^{m}{x_k}^{1+2}=1^3+2^3+4^3+6^3+8^3+10^3=1801 [13]
w_{2,0}=sum_{k=1}^{m}{x_k}^{2+0}=w_{0,2}=221 [14]
w_{2,1}=sum_{k=1}^{m}{x_k}^{2+1}=w_{1,2}=1801 [15]
w_{2,2}=sum_{k=1}^{m}{x_k}^{2+2}=1^4+2^4+4^4+6^4+8^4+10^4=15665 [16]

Współczynniki ostatniej kolumny macierzy:

w_{0,3}=sum_{k=1}^{m}{x_k}^{0}cdot f(x_k)=1cdot 6+1cdot 8 +1cdot 4+1cdot 2+1cdot 0+1cdot 2=22 [17]
w_{1,3}=sum_{k=1}^{m}{x_k}^{1}cdot f(x_k)=1cdot 6+2cdot 8 +4cdot 4+6cdot 2+8cdot 0+10cdot 2=70 [18]
w_{2,3}=sum_{k=1}^{m}{x_k}^{2}cdot f(x_k)=1^2cdot 6+2^2cdot 8 +4^2cdot 4+6^2cdot 2+8^2cdot 0+10^2cdot 2=374 [19]

Najwyższy czas poskładać do kupy macierz:

begin{bmatrix}6 & 31 & 221 & 22\ 31 & 221 & 1801 & 70\ 221 & 1801 & 15665 & 374end{bmatrix} [20]

Nie będę tutaj rozwiązywał tej macierzy, powiem tylko, że jej rozwiązanie daje w wyniku następujące wartości współczynników szukanego wielomianu:

left{ begin{matrix}a_0=9,2196044712\ a_1=-1,7613069647\ a_2=0,0963026655end{matrix}}  right [21]

Funkcja fapr(x)=a0·x0+a1·x1+a2·x2=9,2196044712-1,7613069647·x+0,0963026655·x2 nie należy do najpiękniejszych, ale jak wynika z poniższego wykresu, działa ona bez zarzutu.

wykres aproksymacji
Rys. 1
Wykres aproksymacji punktów metodą najmniejszych kwadratów.

Wykres wygenerowany został w programie wxMaxima za pomocą następującego kodu:

Listing 1
  1. plot2d([9.219604471*x^0-1.761306965*x^1+0.09630266552*x^2,[discrete,[[1, 6],[2, 8],[4, 4],[6, 2],[8, 0],[10, 2]]]],[x,1,10],[style,line,points],[gnuplot_term, "svg size 600,500"], [gnuplot_out_file, "C:\\aproksymacja.svg"],[legend,"fapr(x)=0.09630266552*x^2-1.761306965*x+9.219604471","punkty aproksymowane"]);

I edytowany w programie Inkscape

A na co to komu?

Stosuje się do uzyskania wzoru w postaci prostej funkcji wielomianowej punktów uzyskanych w wyniku przeprowadzanych pomiarów.

Program Aproksymator.exe

Pewnego dnia obudziłem się z przemożną chęcią napisania programu, który po podaniu odpowiednich danych na wejście wypluje mi na powierzchnię ekranu funkcję aproksymującą zadane punkty wielomianem stopnia, który ja podałem. Toteż i zakasałem rękawy i zrobiłem taki właśnie mały programik o dźwięcznej nazwie Aproksymator.exe.

Pragnę nadmienić, że program ten rozwiązanie zapisuje do pliku tekstowego aproksymacja.txt, gdzie w perfidny (żeby nie powiedzieć, że przebiegły) sposób program zapisuje dane wejściowe, funkcję aporoksymującą oraz (jakby tego było mało) kod niezbędny do wygenerowania wykresu punktów i funkcji aproksymującej w programie wxMaxima.

Przykład, rozwiązania wygenerowanego przez mój program rozwiązania dla wcześniej rozwiązywanego zadania z najdzikszą wręcz rozkoszą zamieszczam poniżej:

Listing 2
  1. Oto rozwiązanie aproksymacji wielomianiem 2 stopnia następujących punktów:
  2. P1x= 1
  3. P1y= 6
  4. P2x= 2
  5. P2y= 8
  6. P3x= 4
  7. P3y= 4
  8. P4x= 6
  9. P4y= 2
  10. P5x= 8
  11. P5y= 0
  12. P6x= 10
  13. P6y= 2
  14. Funkcja aproksymujaca zadane punkty przyjmuje postac nastepujaca:
  15. fapr(x)=9.219604471*x^0-1.761306965*x^1+0.09630266552*x^2
  16. Wykres w WxMaximie:
  17. plot2d([9.219604471*x^0-1.761306965*x^1+0.09630266552*x^2,[discrete,[[1, 6],[2, 8],[4, 4],[6, 2],[8, 0],[10, 2]]]],[x,1,10],[style,line,points])

Poniżej krótki filmik pokazujący działanie programu.

Załączniki:

Program Aproksymator do aproksymacji punktów metodą najmniejszych kwadratów

Komentarze