78 8...

Metoda najmniejszych kwadratów
40
35
30
25
20
y
15
10
5
0
-5
-2
0
2
4
6
8
10
x
Rysunek 8.1: Przykład danych zawierających szum.
malizacji funkcji:
n
X
E =
d 2( xi) .
(8.2)
i=1
Jeśli założymy że funkcja g( x) dana jest przez wielomian m-tego stopnia:
g( x) = a 0 + a 1 x + a 2 x 2 + · · · + amxm, (8.3)
to można zapisać:
n
n
n
X
X
X
E =
|f( xi) − g( xi) | 2 =
|g( xi) − f( xi) | 2 =
( g( xi) − f( xi))2
i=1
i=1
i=1
n
= X( a 0 + a 1 xi + a 2 x 2 +
i
· · · + amxm
i
− f( xi))2 .
(8.4)
i=1
Minimalizacja funkcji E może być przeprowadzona przez przyrównanie do zera
pochodnych cząstkowych funkcji E względem współczynników ai : i = 0 , 1 , . . . , m:
∂E = 0 ,
∂a 0
∂E = 0 ,
∂a 1
8.2. Dopasowanie funkcji liniowej
79
...
∂E = 0 .
(8.5)
∂am
Dowód prawdziwości tego stwierdzenia wykracza poza ramy niniejszej pozycji, więc
nie zostanie przytoczony. Wzory (8.5) dają m + 1 równań z m + 1 niewiadomymi ai : i = 0 , 1 , . . . , m. Rozważając pierwsze równanie (8.5) można zapisać: n
∂E
∂
=
X( a
+ · · · + a
∂a
0 + a 1 xi + a 2 x 2
i
mxm
i
− f( xi))2
0
∂a 0 i=1
n
∂
= X
( a
+ · · · + a
∂a
0 + a 1 xi + a 2 x 2
i
mxm
i
− f( xi))2
0
i=1
n
= X 2( a 0 + a 1 xi + a 2 x 2 +
i
· · · + amxm
i
− f( xi))
i=1

∂

( a
+ · · · + a
∂a
0 + a 1 xi + a 2 x 2
i
mxm
i
− f( xi))
0
n
= X 2( a 0 + a 1 xi + a 2 x 2 +
i
· · · + amxm
i
− f( xi))(1)
i=1

n
!

n
!

n
!
n
=
X
X
X
X
na 0 +
xi a 1 +
x 2
a
xm
a
f ( x
i
2 + · · · +
i
m =
i) .
i=1
i=1
i=1
i=1
(8.6)
W podobny sposób można wyprowadzić równanie ∂E/∂a 1, otrzymując:

n
!

n
!

n
!
n
X
X
X
X
xi a 0 +
x 2
a
xm+1
=
x
i
1 + · · · +
i
if ( xi) .
(8.7)
i=1
i=1
i=1
i=1
Rozwiązując w podobny sposób pozostałe równania otrzymuje się układ równań:

n
ψ( x
 



i)
ψ( x 2)
. . .
ψ( xm)
i
i
a 0
ψ( f ( xi))
ψ( x
)
ψ( x 3)
. . . ψ( xm+1)

i)
ψ( x 2 i
i
a
ψ( x
i
 
1 

i f ( xi)) 

)
)
)
) 



 ψ( x 2
ψ( x 3
ψ( x 4
. . . ψ( xm+2
a
ψ( x 2 f ( x
i
i
i
i
 
2  = 
i
i))  ,
(8.8)

.
.
.
.
.
 
. 

.


..
..
..
. .
..
 
..  
..


 



ψ( xm) ψ( xm+1) ψ( xm+2)
. . .
ψ( x 2 m)
a
ψ( xmf ( x
i
i
i
i
m
i
i))
gdzie: ψ( ·) = P n (
i=1 ·). Taki układ równań może być rozwiązany przy użyciu metody
eliminacji Gaussa.
8.2
Dopasowanie funkcji liniowej
Jak już zostało wspomniane wielomiany relatywnie niskiego stopnia są naj-
bardziej użyteczne przy aproksymacji funkcji. Okazuje się, że najczęściej używaną
80
8. Metoda najmniejszych kwadratów
funkcją do aproksymacji jest linia prosta. Nawet jeśli charakterystyka danych nie
jest liniowa, zawsze można przeskalować wykres tak aby uzyskać liniową charakte-
rystykę wyznaczanej funkcji (np. za pomocą skali logarytmicznej).
Niech m = 1 oraz ψ( ·) = P n (
i=1 ·), równanie (8.8) przyjmuje postać:

n
ψ( x


i )
a 0 = ψ( f( xi)) .
(8.9)
ψ( xi) ψ( x 2)
a
ψ( x
i
1
if ( xi))
Mnożąc strony równania przez macierz odwrotną oraz korzystając z algorytmu
obliczającego macierz odwrotną1 otrzymuje się:
a

− 1

0
=
n
ψ( xi)
ψ( f ( xi))
a 1
ψ( xi) ψ( x 2)
ψ( x
i
if ( xi))
1

)


=
ψ( x 2
ψ( f ( x
i
−ψ( xi)
i ))
nψ( x 2)
−ψ( x
ψ( x
i
− ( ψxi)2
i)
n
if ( xi))
1

)

=
ψ( x 2 ψ( f ( x
i
i )) − ψ( xi) ψ( xif ( xi)) .
(8.10)
nψ( x 2)
nψ( x
i
− ( ψ( xi))2
i f ( xi)) − ψ( xi) ψ( f ( xi))
Co ostatecznie prowadzi do:
(P n x 2)(P n f( x
x
x
a
i=1
i
i=1
i)) − (P n
i=1
i)(P n
i=1
if ( xi))
0 =
,
(8.11)
n P n
x 2
x
i=1
i − (P n
i=1
i)2
n P n
x
x
f ( x
a
i=1
if ( xi) − (P n
i=1
i)(P n
i=1
i))
1 =