Моделирование данных при помощи кривых для восстановления пробелов в таблицах

/

.

. . .

,

,

, 1998. 205 .

. . !" 660036, -36, # !" , E-mail: [email protected]

(

). .

– .

1. -

n

– 2 -1

.!

n-

M ."

x k

L x,

k-

k

#

,

. Px⊂Lx. $

Lx # PrM(x) –

x(

Lx

Px)

– ImM(x) – Px). %

&

$ %

M, M

x

,

, :

ImM(x),

&( $

#) –

x

#

,

Lx ( #

M –

#

:

PrM(x).

,

. ' ( .

, –

) x(

Lx .

Px)

M #

PrM(x).

& #. "

. ., #

, . .

http://neuroschool.narod.ru

/

*

2. *+ )

.

. . .

!" ##

%$,

&' (#$ )

,

, 1998. 205 .

* # #

'

##$

" , # #

@, #

.( .

:

$ %

%

%

' ; ' –

, ,

; %

%

'

# ,

, (

,

&

).

& ( "

%

'

–%

(

)

%

)

. '

%

%

'

xiyj+bj. A=(aij). % A

xiyj+bj

:

(aij − xi y j − b j ) 2 → min .

Φ=

(1)

i, j aij ≠ @ )

xi, yj

bj,

.* ,

, , .!

,

yj #

+

,

,

. .(

,

xi,

)–&

,

bj –

,

. yj

bj

∂Φ/∂xi=0

#

xi =

,

#

xi, #

(1),

:

( y j )2 .

(aij − b j ) y j j aij ≠ @

j aij ≠ @

xi

yj ∂Φ/∂yj=0

# j

http://neuroschool.narod.ru

bj, ∂Φ/∂bj=0

#

(1),

#

: yj

bj:

/ j j y j A01 + b j A00 = Boj j j y j A11 + b j A10 = B1j

.

Aklj =

,

"

. . .

,

xik + l , Bkj =

i aij ≠@

,

, 1998. 205 .

aij xik , k=0..1, l=0..1. i aij ≠@

bj

,

:

j j j A10 B1 − B0 j j B0j − y j A01 A00 , bj = . yj = j j A00 j j A10 − A01 A11 j A00 , : y 2j = 1 ) y– , 1( . . j

bj =

1 nj

nj =

aij , i aij ≠@

1 (

j-

), . . bj

i aij ≠ @ .

-

∆Φ/Φ, ." ,

– Φ, Φ – :

Φ. $ ε, δ<0.

∆Φ – ∆Φ/Φ<ε

–

Φ<δ

A. A

P1 &

A-P1

P2

,

. .-

xiyj+bj.

, ,

.

Q-

Q xiyj+bj,

Q-

“

”

–

Q

xiyj+bj. Pq

q q q xiyj+bj ( Pq = xi y j + b j ),

$

#

#

# (

# aj=@).

a qj : a 0j = a j (a j ≠ @) ;

http://neuroschool.narod.ru

q

#.

A aj

q

x (a)

/

x1 (a ) =

.

. . .

(a 0j − b1j ) y1j

,

,

, 1998. 205 .

( y1j ) 2 ;

j a j ≠@

j a j ≠@

a1j = a 0j − b1j − x1 ( a ) y1j (a j ≠ @) ; ……………..

(2)

x q (a ) = j a j ≠@

( a qj −1 − b qj ) y qj

j a j ≠@

( y qj ) 2 ;

a qj = a qj −1 − b qj − x q ( a ) y qj (a j ≠ @) ; …………….. *

M–

,

zj=tyj+bj,

#

M PrM(a)

(2):

Pr(a)=t(a)yj+bj;

t (a ) =

( y j )2 .

(a j − b j ) y j j a j ≠@

QQ

aj =

j a j ≠@

:

q =1

x q ( a ) y qj + b qj , (a j ≠ @) .

)

(4)

# , #

– q q q=2, Pq = xi y j (b=0). " . , ,

( &

(3)

."&

,

& , #

). '

(

, #

,

, &

,

,

.

3. ( ,"'"# %#$ - )

$"-

+'$

' ( , #

http://neuroschool.narod.ru

' ( ).

# )

# .

/

.

. . .

,

, 1998. 205 . A.

# . –

,

.

* ' !" ( &' ."( #" ) f(t),

( aij − f j ( aik yk )) 2 + α

Φ=

,

(1).

(y,b)=0, (y,y)=1 – &

%

,

, , &

#

,

i, j aij ≠ @

k

+∞

#

:

( f ′′(t )) 2 dt ,

α>0 –

.

−∞

&

, .

/) "

* ' !" f(t) &

%

. f(t) &

-

{tk}

( ) #

#

f (t ) ≈ ty + b +

# &

-

#

# zj=tyj+bj -

[1] ( f(t)

ty+b).

m ( e λt k + e λt j )( e λt − e λt j ) , + ( f ( tk ) − t k y − b ) ∏ λt λt k λ t λ t λ t λ ( e + e )(t − tk ) j =1 ( e k − e j )( e λt + e j ) k =1 j ≠k λ– , # , , & (& π/λ).

2( e λt − e λtk )

m

#

* ' !"

(5)

&' ."( #" xi

aij

[-1,1]. " # .

, ,

#

* ' !" * '"#

,

* #" n

"

n j n A f j ( x ) = f n x + f nj−1x n −1 + ... + f1j x + f 0j , . .: +∞ 2 α>0 – Φ= ( aij − f j ( aik yk )) + α ( f ′′(t )) 2 dt , i, j k −∞ aij ≠ @

(

xi=(ai,y), &

),

http://neuroschool.narod.ru

ai – i&

A,

.

(

f kj (k=0..n),

#

/

.

Φ, #

. . .

,

,

, 1998. 205 .

∂Φ ∂f kj = 0 (k=0..n)

#

:

"

: n

f j ′ (t ) =

kf kj x k −1 , f j ″ (t ) =

k =1 n 2

( f j ″ (t ) )

=

(

,

n

k ( k − 1) f kj x k − 2 ,

:

k =2

k ( k − 1)l (l − 1) f kj f l j x k + l − 4 . %

,

k ,l = 2

[-1,1]):

)

(

+1

x k + l −3 f j ″ (t ) dt = f kj f l j k ( k − 1)l (l − 1) = k + l − 3 k ,l = 2 −1 −1 . n 2 j j = f k f l k ( k − 1)l (l − 1) k +l −3 k ,l = 2 +1

n

k +l -

(

: d +1 ″ f j (t ) dt = df kj −1

)

(

$

,

∂Φ ∂f kj

= −2 i aij ≠ @

+

.

n

l =2 l ≠k k +l k=0..n, : n (aij − f l j xil ) xik + l =0

n l =2 l ≠k k +l -

2 2 f l k ( k − 1)l (l − 1) + 2 f kj k 2 ( k − 1) 2 =0 k +l −3 2k − 3 f kj (k=0..n),

Aklj (0) f l j = Bkj (0) ,

k=0..n,

0 xik + l + 2k 2 (k − 1) 2 i aij ≠ @

:

,

2 , 2k − 3 2 k (k − 1)l (l − 1) , k +l −3

http://neuroschool.narod.ru

.

:

l =0

Aklj (0) =

2 2 . + 2 f kj k 2 (k − 1) 2 k +l −3 2k − 3

j

& n

f l j k ( k − 1)l (l − 1)

k<2 l<2 k =l k ≠l

k +l ,

/

Bkj (0) =

"

.

. . .

,

,

, 1998. 205 .

aij xik . i aij ≠@ 1-

f 0j

,

: n

f 0j =

j A0jl (0) f l j + A00 (0) f 0j = B0j (0)

l =1

n

Aklj (0) f l j + Akj0 (0)

n

B0j (0) −

A0jl (0) f l j

l =1 j (0) A00

l =1

B0j (0) −

n

A0jl (0) f l j

l =1 j A00 ( 0)

= Bkj (0)

.$ #

k=1..n,

j Akj0 (0) j j j j j Ak 0 (0) Akl (0) − A0l (0) f l = Bk (0) − B0 , j j A00 (0) A00 (0) l =1 / # : n

Akj0 (0) j j j Akl (1) = Akl (0) − A0l (0) , j A00 (0)

n

Aklj (1) f l j = Bkj (1) , l =1

k=1..n.

k=1..n,

j j j j Ak 0 (0) Bk (1) = Bk (0) − B0 . j A00 (0) (

f1 j

# #

m n

,

Aklj ( m ) f l j = Bkj ( m ) ,

. . :

k=m..n. 0

l =m

f mj

(k=m)

."

:

f mj =

Bmj (m ) −

n

j Aml (m) f l j

l = m +1 j Amm (m)

,

j j Akm (m) j j j j j Akm ( m ) , Akl ( m) − Aml ( m ) f l = Bk (m ) − Bm j j Amm ( m) Amm ( m ) l = m +1 % : n Aklj (m + 1) f l j = Bkj (m + 1) , k=m+1..n, l = m +1 n

http://neuroschool.narod.ru

k=m+1..n.

:

/

.

. . .

,

,

, 1998. 205 .

j j Akm (m) Akm ( m) j j j j j j , Bk ( m + 1) = Bk ( m ) − Bm ( m ) . Akl ( m + 1) = Akl (m ) − Aml (m ) j j Amm (m) Amm ( m) f kj (k=0..n) # ( , : Aklj (0) = xik + l , Bkj (0) = aij xik , i i aij ≠ @ aij ≠@ j j Akm (m) Akm ( m) j j j j j j , Bk ( m + 1) = Bk ( m ) − Bm ( m ) , Akl ( m + 1) = Akl (m ) − Aml (m ) j j Amm ( m ) Amm ( m) n j Bk ( k ) − Aklj ( k ) f l j l = k +1 , k=n..0. f kj = j Akk (k )

#

* ' !" )+ "0 )" " *' %#

"

(

# :

( aij − f j ( aik yk )) 2 + α

Φ= i, j aij ≠ @

k

&

+∞

( f ′′(t )) 2 dt ,

[-1,1]. 1

n

: − 1 = x0 < x1 < ... < xn −1 < xn = 1 . & x = x − x s −1 , xs −1 < x < xs , s=1..n, 3 3 2 f ( x ) = f s 3 x + f s 2 x + f s1 x + f s 0 = f sl x l . l =0 : 3 3 f ′( x ) = lf sl x l , f ′′( x ) = l (l − 1) f sl x l . l =1 l =2 * & : 2 1 n −1 x s 3 2 I = ( f ′′(t ) ) dt = l (l − 1) f sl t dt = s =1 x s −1 l = 2 −1 xs

t k +l −3 = f sk f sl k (k − 1)l (l − 1) = k + l − 3 s =1 k ,l = 2 x s −1 3

n −1

3

k + l −3

h = f sk f sl k (k − 1)l (l − 1) s k +l −3 s =1 k ,l = 2 http://neuroschool.narod.ru

α>0 –

.

−∞

s=0..n,

n −1

#

: hs = x s − x s −1 . :

xs ,

/

.

. . .

,

,

, 1998. 205 .

( , Φ=H+αI→min,

# n −1

3

: k +l −3

3

h ai − f sl xil , I = f sk f sl k ( k − 1)l (l − 1) s . k +l −3 l =0 s =1 k ,l = 2

H= i ai ≠ @

. &

#

f ( x s − 0) = f ( x s + 0) f ′( x s − 0) = f ′( x s + 0) , f ′′( x s − 0) = f ′′( x s + 0)

#

:

s=1..n-1.

#

&

,

:

f s +1,0 = f s 3hs3 + f s 2 hs2 + f s1hs + f s 0 f s +1,1 = 3 f s 3hs2 + 2 f s 2 hs + f s1 f s +1,2 = 3 f s 3hs + f s 2

,

s=1..n-1.

'

2

L=Φ+

n −1

λs 0ϕ s0 +

s =1

n −1

λs1ϕ s1 +

:

n −1

λs 2ϕ s 2 ,

:

s =1 s =1 3 2 ϕ s 0 = f s +1,0 − f s 3hs − f s 2hs − f s1hs − f s 0

ϕ s1 = f s +1,1 − 3 f s 3hs2 − 2 f s 2 hs − f s1 ϕ s 2 = f s +1,2 − 3 f s 3hs − f s 2

,

s=1..n, –

,

. ,

#

#

:

∂L = 0, ∂f sl

l = 0..3, s = 1..n

∂L = 0, ∂λsl

l = 0..2, s = 1..n − 1

, . .

(7n-3)

(7n-3)

. &

∂L ∂H ∂I = +α + Lsl , ∂f sl ∂f sl ∂f sl

http://neuroschool.narod.ru

# :

:

/

∂H = −2 ∂f sl i

.

ai −

ai ≠ @

3

. . .

,

,

, 1998. 205 .

f sp xip xil ,

p =0

3 ∂I 2 2 = f sk k (k − 1)l (l − 1) + 2 f sl l 2 (l − 1) 2 , ∂f sl k = 2 k +l −3 2l − 3 k ≠l

Ls 0 = λs −1,0 − λs 0 Ls1 = λs −1,1 − λs 0hs − λs1 Ls 2 = λs −1,2 − λs 0hs2 − λs1 2hs − λs 2

&

,

&

s-1

Ls 3 = − λs 0hs3 − λs1 3hs2 − λs 2 3hs &

s=2..n,

&

s ,

#

-

s=1..n-1. ,

,

,

#

((7n-3)×(7n-3)), .

&

,

.

/) ,

* ' !" &

:

-

,

& &

,

-

, .%

( &

"

&

"

),

.

/)

* ' !" *

$ "

&

&

#

[-1,1] .

#

/) % 3 #

* ' !" * " * # #( , (5) ,

"+' & # ,

'

# f(t)

#&

ty+b.

# , & #

(5)

,

[1]). '

(

( a f(t). ( (3),

'1#

1 )( ,"'"# %#$ - ) ( f(t), # (" f((a,y)), & # # Pr(a)=ty+b, t=(a,y), – – # f(t) t=t(a). f(t) # xiyj+bj

http://neuroschool.narod.ru

,

") :

.

/

.

. . .

–&

,

,

-

,

, 1998. 205 .

. .,

#. &

,

A=(aij) P q = xiq y qj + b qj (

q

aij , q q

q q

(y ,b )=0, (y ,y )=1 – &

q

f (t).

)

/

#

:

aij0 = aij , P q = xiq y qj + b qj –

(

(1))

aijq −1 ,

tiq =

j aij ≠ @

( aijq −1 − b qj ) y qj

q

f (t)

j aij ≠ @

&

{t qj }

(6)

ϕ qj (t ) ,

: #

:

ϕ qj (tiq ) = aijq −1 ,

aijq −1 ≠ @

aijq −1 = @ , –

ϕ qj (tiq ) = xiq y qj + b qj , &

#

(5). q t j : aijq = aijq −1 − f jq (tiq ) . aij ≅ f jq (tiq ) . ) q , aijq = @ , :

q

#

( y qj ) 2 ,

f (t)

"

.!

aij≠@,

?% & %

&, &

$ 0

&

, &

: *

%

(

) )

&. , #

A=

A1

0

...

0

0

A2 ...

0

...

...

...

...

0

0

...

An

-

:

,

(7)

&

0– – $ "

http://neuroschool.narod.ru

. , (" "

. ") .4

–

/

.

. . .

,

,

( ,

4.

, 1998. 205 . -

).

%

##$% ) #( % # (

("

#. %

q

–

y ),

q

") –

b

fq(t) n

n

, (5).

"

"

a

(

t(a) ( f jq (t ( a )) (aj≠@)

)

:

(3)

q

&

),

# f (t(a)),

#

.

a

f jq (t ( a )) (aj=@). $

& #

–

.

f jq (t ( a )) j. %

(

.1) (

[2]) –

n

(

).

(

α0 α1 α2 ... αn

(3) – # ( , ). &

Σ

f2

α

#

fn ,

, #

( – (

-

. 1.

), . .

# "

# ,

...

(

"

.'

(1)),

f1

( #

), ,

& ,

(

) .

0

0.,. .

#

%.".

. 1 " "',().106'7" (

", 5 68,

http://neuroschool.narod.ru

. 2.1.).

13 ( 5 05.04.1291) 36

/

.

. . .

,

,

, 1998. 205 .

2 1. 0 , 2. . , 3. .

2.0. 3 :, 0.,., 1 :, 0.,.,

# 1998. ( 1998. %. 74. 4. . 0.,.,

. , 1990. 248 . .0. , , 1996. 256 . %."., 1 0.0. ' // ( (', 1' -98) ( %.2.% . 4. V. , :' %."., 1

// V ,

http://neuroschool.narod.ru

. %. 53.

#

). ,

.

,

'

,

0.0. , "

1998. (

.

,

#

,

",