Numerische Mathematik, 7., uberarbeitete Auflage 9783834806833, 3834806838 [PDF]

148 63 27MB

German Pages 589 [588]

Report DMCA / Copyright

DOWNLOAD PDF FILE

Papiere empfehlen

Numerische Mathematik [7ed.] 9783834806833, 3834806838

122 11 8MB Read more

Numerische Mathematik [7ed.] 9783834806833, 3834806838

110 24 4MB Read more

Numerische Mathematik I

107 94 584KB Read more

Einfuehrung in die numerische Mathematik [3ed.]

103 64 3MB Read more

Unternehmensbewertung, 5. uberarbeitete und erweiterte Auflage 3800632705, 9783800632701

108 96 3MB Read more

Numerische Mathematik 1 [Vorlesungsskript, web draft ed.]

105 26 1MB Read more

Numerische Mathematik 2: eine Einfuehrung [5. Aufl.] 3540237771, 9783540237778

114 104 2MB Read more

Band 1. Einfuehrung in die numerische Mathematik 9783446123908, 3446123903

118 36 2MB Read more

Einfuehrung in die numerische Mathematik [Band 2. ] 3446125566

117 21 2MB Read more

Numerische Mathematik 1: eine Einfuehrung [9. Aufl.] 3540213953, 9783540213956

122 33 2MB Read more

Numerische Mathematik, 7., uberarbeitete Auflage
9783834806833, 3834806838 [PDF]

Author / Uploaded
Hans Rudolf Schwarz
Norbert Kockler

0 0 0
Gefällt Ihnen dieses papier und der download? Sie können Ihre eigene PDF-Datei in wenigen Minuten kostenlos online veröffentlichen! Anmelden

Datei wird geladen, bitte warten...

Zitiervorschau

Hans Rudolf Schwarz | Norbert Köckler Numerische Mathematik

Hans Rudolf Schwarz | Norbert Köckler

Numerische Mathematik 7., überarbeitete Auflage STUDIUM

Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über abrufbar.

Prof. Dr. Hans Rudolf Schwarz Universität Zürich Mathematisch-Naturwissenschaftliche Fakultät (MNF) Winterthurerstrasse 190 8057 Zürich Prof. Dr. Norbert Köckler Universität Paderborn Fakultät EIM – Institut für Mathematik 33098 Paderborn [email protected]

1. Auflage 1986 6., überarbeitete Auflage 2006 7., überarbeitete Auflage 2009 Alle Rechte vorbehalten © Vieweg +Teubner |GWV Fachverlage GmbH, Wiesbaden 2009 Lektorat: Ulrike Schmickler-Hirzebruch |Susanne Jahnel Vieweg +Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.viewegteubner.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: MercedesDruck, Berlin Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-0683-3

! " #$ % & % ! ' ( ) ( * # + " ! , % - ! . % +% % / & * 0 - % ! . - 0 / / 1 ! 1 " % /21/ - + ! , % ' 1 . 3 / & + ' % 1 / 4 5 ! / ( 1 6778

& 9 0 : 0 & ! ' ( ' : , % ( - +( ; / ! "! #! 1 / ! "! ;! #! 1%( - + ( # + < % ! ' # = ! " ( ( 9 * ! , 0 % ! " '

0 $ % ( ( " 0 % $ (

, ' $ + ! " ( + ( 9 2 ! , 1 ( + - ' > ! ; 1% 2 % ( ; 1 1 * - + :

( 0 1 2 % " 1 ( 09 - + ? 9 ! & / ! "! 1 ,*, : " ? % % 0( % - + 0 ! / ( 1 677@

! " # "" " $

%&' ( ! ) * + " )

, ! ! ) ) " - -

! . / ! 0 1 2 3

" + ! " -

- 4 ( " ) ! -

2 , 1 ,

+! " 5

" 3

! 1 ,

"

0 / 1 - "

(

" 1 6 5 . ) * (! , ! # 7 / ! 8 6

+!

%9 %: " 4 + ! ; " 1 - ! ! - ! +

)1- - 2 +

- ) 6 ( 7! 1 ! / ! - +8 " + 0 " .

! 6 " - 5 1 " ! ! "4 0 " 1 / 4 ( 2

! - ? " " , 7 ) 4 ( 2 " + / ! 9@@& 5 "

!" #

$

$

%&

'()%" * * " , -. * &- /0"

+ +

' . , &- 1"* &- , 2" "

$ $

! * * - !** -, " 0 3 ! * - 4" '- *

5 6 5. "- /- 5" & ! * 4" '- *

$ $

% #

!" #

$

$

%&

!

" # $

%& '( )

* +%& * -* .# +%& -*

! ,

/ #

* 0& - 1 -2%& 1

+

+ # 34%& -5)

-

-5) ' ' 6 7" & -5) + -5) 34%&

, , ,

! ! !

.8"9 '2 .8"9 + %& .8"9

, , ,

1

%& "9 3 : & ;> ( F I C=G# $ % * % & ( ( 9 2 9 D( >C 2 C4 $ = $ F3 !

CC F= F8G# $ #

! "# $ ! % & ' " (

)% % %

* # "

+ , - * & " * # . $ % /&

( /& '

% e* 0"

* % $ 12 ' $% % % * % % 3 4% "

" # # '

' 3 4 * " % /& 5 ' * &1 " & " & (6 7 , 8 ( % , % * ( x % x˜ ∈ R )( , x 2 δx := x ˜−x

++

x x = 0 x ˜−x εx := x x

M R !"""# $ x ∈ M x = (x) · a · E e−k .

%

& ' M (( ) * • E ∈ N E > 1 E = 2 • k ∈ N • emin ≤ e ≤ emax emin , emax ∈ Z

& a ∈ N0 +

,

a = a1 E k−1 + a2 E k−2 + · · · + ak−1 E 1 + ak E 0 ;

- 0 ≤ a ≤ E − 1 & k . ai / ' 0 & ' 1 & # 2 x = 0 / k

E k−1 ≤ a < E k , x = 0.

3 ½

x 4 k E & 4 k

& 567( x = 0* E emin −1 ≤ |x| ≤ E emax (1 − E −k ).

" $ " ' M .8 ! & ' 6 9 $6( : 7

0

0.5

1

2

3

4

5

6

7

E = 2 k = 3 emin = −1 emax = 3

9 6 $ " x + ; rd(x) 4 + $ * E τ := E −k .

0 x E k−1 ≤ μ ≤ E k − 1.

x = μE e−k ,

x ¾ y1 = μE e−k y2 = μE e−k

rd(x) = y1 rd(x) = y2 ! |rd(x) − x| ≤

E e−k y 2 − y1 ≤ . 2 2

" e−k

E |rd(x) − x| 1 2 ≤ = E 1−k = τ. e−k |x| μE 2

x = π y = x2 = 9.8696044 . . .

0 1 ! E = 10 k = 2 " τ = 0.05 rd(π)

=

3.1 = 0.31 · 101

rd(π) rd(π)

=

0.961 · 101

y10,2

=

rd{rd(π) rd(π)} = 0.96 · 101 = 9.6

2

≈

0.27.

y10,2 − π

! E = 2 k = 5 " τ = 2−5 = 0.03125 rd(π)

=

rd(21 + 20 + 2−3 + 2−6 + · · ·) = 21 + 20 + 2−3 = 0.11001 · 22

rd(π) rd(π)

=

0.1001110001 · 24

y2,5

=

rd{rd(π) rd(π)} = 0.10100 · 24 = 10

y2,5 − π 2

≈

0.13.

# $%%%& ' &( ) ¾ μ

μ μ

μ

E = 2

t 24 53

emin −125 −1021

emax 128 1024

τ 2−24 ≈ 6 × 10−8 2−53 ≈ 1 × 10−16 2−64 ≈ 5 × 10−20

τ rd(x) = x(1 + ε) |ε| ≤ τ. ∗ rd(x ∗ y) = (x ∗ y)(1 + ε) |ε| ≤ τ. τ g rd(1 + g) > 1.

! "! !

! " # $ % & $ ' ( # k ! " ) & *+ k , $ $- +$ $ $ & .$ / 0 $ 1 $ $ & k , $ $% $ )$ % & $ ,& 2 # 32 1$ &- $ $ 45 $ 6 0 $ ,& - $ * 1 $ 7 0 8$ 2 ( 0$9

a := 1.2 b := 1.1 ! a2 − b2 = (a + b) (a − b) " # ! 2

a2 = 1.44

=⇒

rd(a2 ) = 1.4

b2 = 1.21

=⇒

rd(b2 ) = 1.2

2

rd(a ) − rd(b )

=

0.2

$ % &'.

( ) * # a + b = rd(a + b)

=

2.3

a − b = rd(a − b)

=

0.10

(a + b)(a − b)

=

0.23

$ + &'.

√ √ √ 99 − 70 2 = 9801 − 9800 = √

1 √ = 0.005050633883346584 . . . . 9801 + 9800

k!

" #$ % & % k √ √ √ √ √

99 − 70 2 9801 − 9800 1/( 9801 + 9800) 2 4 6 10

1.0 0.02000 0.00530000 0.005050660000

0.0 0.01000 0.00510000 0.005050640000

0.0050 0.005051 0.00505063 0.005050633884

" $ ' ( )

*

% ' + ,

x ∈ Rm y ∈ Rn

y = ϕ(x)

! " # $ % & '% %()* + ' * ' $ & , - *. % / ¿

δx ∈ Rm x ⎞ ⎛ ∂ϕ1 ∂ϕ1 ··· ⎜ ∂x1 ∂xm ⎟ ⎜ ⎟ n,m ⎟ Dϕ = ⎜ ⎟∈R ⎜ ⎝ ∂ϕ ∂ϕn ⎠ n ··· ∂x1 ∂xm ϕ

0

!

! " # y = ϕ(x) $% & . δy = Dϕ δx , εyi

. =

m

Kik εxk ,

1

i = 1, · · · , n.

k=1

Kik 2 * ∂ϕi (x) xk , i = 1, · · · , n, k = 1, · · · , m. Kik = ∂xk ϕi (x)

3

'! , %# δy % 4* + 5 1 %# εy + ,

=.

! !"#"$% !"#"&% δ # ε %#

¿

x

xk

˙ |δyi | ≤

m k=1

˙ |εyi | ≤

m

∂ϕi (x) , |δxk | ∂xk

! i = 1, · · · , n,

"!

|Kik | |εxk |.

k=1

y = ϕ(x1 , x2 , x3 ) = x1 + x2 + x3 , 3

ϕ : R → R ∂y = 1 j = 1, 2, 3. ∂xj xj K1j = , j = 1, 2, 3. x1 + x2 + x3 P xi xj

δy = δx1 + δx2 + δx3

x1 x2 x3 εx + εx + εx . x1 + x2 + x3 1 x1 + x2 + x3 2 x1 + x2 + x3 3 |εxj | ≤ τ

εy =

|εy | ≤

|x1 | + |x2 | + |x3 | τ. |x1 + x2 + x3 |

x1 + x2 + x3

y = x1 ± x2

⇒

δ y = δx 1 ± δx 2

y = x1 · x2 x1 y= x2

⇒

δy = x2 δx1 + x1 δx2 + δx1 δx2 . x2 δx1 − x1 δx2 δy = (x2 = 0) x22

⇒

. = x2 δx1 + x1 δx2

εx1 ±x2 εx1 ·x2

= . =

x1 x2 εx1 ± εx x1 ± x2 x1 ± x2 2 εx1 + εx2

(x1 ± x2 = 0)

εx1 /x2

. =

εx1 − εx2

εxn

. =

n εx ,

n ∈ Q,

. 1 ε√x = εx ) 2

x1 x2 x1 ≈ x2 εx1 −x2 εxi

! " #$ % & '$ ( ) * & +& % * , & -. % & %( - / 0

x = x(0) −→ ϕ(0) (x(0) ) =: x(1) → · · · → ϕ(r) (x(r) ) =: x(r+1) ≡ y x∈R

m

−→ y = ϕ(x) ∈ R

n

+ "$1 %-( 2 ψ

ψ (k)

:=

ϕ(r) ◦ ϕ(r−1) ◦ .. ◦ ϕ(k) : Rmk → Rn ,

(k−1)

=

ψ (k) ◦ ϕ(k−1) ,

3

k = 2, . . . , r.

δx

k

! δy . δy = Dϕ(x) δx + Dψ (1) (x(1) ) E1 x(1) + · · · + Dψ (r) (x(r) )Er x(r) + Er+1 y

. δy = Dϕ(x) δx

+

r

Dψ (i) (x(i) )Ei x(i)

i=1

+

Er+1 y

.

Dϕ, Dψ (i) !"

⎛

⎜ ⎜ Ei := ⎜ ⎝

⎟ ⎟ (i) ⎟ |εj | ≤ τ. ⎠

(i)

ε2

(i)

ε mi

67 839/

: &' ) $ D(f ◦ g)(x) = Df (g(x)) Dg(x) &

Dϕ(x)

Ei #

⎞

(i)

ε1

4

= Dϕ(r) (x(r) ) Dϕ(r−1) (x(r−1) ) · · · Dϕ(0) (x),

5

Dψ (k) (x(k) )

= Dϕ(r) (·) · · · Dϕ(k) (·).

!"# $ ## Dϕ(i) % $ &#$# $ $ '

δx(1) (1)

α

(1) αj (1) | εj

|

. =

Dϕ(0) (x) δx + α(1) (0)

:= rd (ϕ =

(1) εj

≤

τ.

(˜ x)) − ϕ

(0)

(0) ϕj (˜ x)

(˜ x) $ !

(1) (1)

= εj xj

(1)

(1)

(1)

m1 ,m1

$ εj # ( E1 = $ (ε1 , ε2 , . . . , ε(1) m1 ) ∈ R # % m1 ,m1 α(1) , x(1) ∈ Rm . 1 , E1 ∈ R

α(1) = E1 x(1) ,

. δx(2) = Dϕ(1) (x(1) )[ Dϕ(0) (x) δx + α(1) ] + α(2) ,

# # &#$#

!"

$ $ ) # Dk := Dϕ(k) (x(k) ) . δx(2) = D1 D0 δx + D1 α(1) + α(2) .

* ! $ . δx(3) = D2 D1 D0 δx + D2 D1 α(1) + D2 α(2) + α(3) .

+ δy = δx(r+1)

. =

} !"

⎫ Dr Dr−1 · · · D1 α(1) ⎪ ⎪ ⎬ Dr Dr−1 · · · D2 α(2) !" &#$#

⎪ ··· ⎪ ⎭ Dr α(r) α(r+1) * #$#

Dr Dr−1 · · · D0 δx + + + + +

α(r+1) = Er+1 x(r+1) = Er+1 y , $ -

(k) ! εj Ek

" ! # τ r ˙ τ |δy |≤ |Dψ (i) (x(i) )| |x(i) | + |Dϕ(x)| |δx | + τ |y|. $% i=1

" & ' ' ( ) * (i) xk + , k + (i+1) (i) (i+1) Ei - xk = xj εk = 0 " . , / 0 1 . ( * $% ' 2

( 3 '

, ' " # ' '

1 − 11 −+ xx = 1 2x +x

x(0) x

(1)

x ∈R ! (1) x1 = ϕ(0) (x) = (1) x2

= =

(1)

x1

1−x 1+x

: R → R2

: R2 → R

x(2)

=

ϕ(1) (x(1) ) =

x(3)

=

ϕ(2) (x(2) ) = 1 − x(2) : R → R.

(1) x2

!

0 1 ! (1) −x 1 −1 Dϕ(0) = , Dϕ(1) = @ (1) , (1)1 A, +1 x2 (x2 )2 2 Dϕ = , (1 + x)2 Dψ (2) Dψ (1)

= = (j)

Dϕ(2) = −1,

0

Dϕ(2) Dϕ(1) = @−

1 (1)

x2

(1)

,

x1

(1)

(x2 )2

Dϕ(2) = −1,

1 A.

! xk "! x # $ %&' . δy = Dϕ δx + Dψ (1) E1 x(1) + Dψ (2) E2 x(2) + E3 y ! ! „ « (1) 1 1−x 2δx 1−x 0 ε1 + − , = (1) (1 + x)2 1 + x (1 + x)2 1+x 0 ε2 « „ 1−x (2) 1 − x (3) + (−1) ε1 + ε1 1− 1+x 1+x « „ −(1 − x) (1) 2δx 1−x 1 − x2 (1) (2) 1 − x (3) = ε + ε . 1 − + + ε − ε 1 1 1 (1 + x)2 1+x (1 + x)2 2 1+x 1+x

|x| 1, τ |x| , |δx | ≤ τ 1 − x ≈ 1 + x ≈ 1 ˙
0 (1) (1) = (aik ) ∈ R(n−1),(n−1) aik "#

$%&'

()* A 2 ? @ " ;$ x(1) = (x2 , x3 , . . . , xn )T = 0 $

x1

a11 > 0 l11 = 0

n

li1 xi = 0

i=1

x = (x1 , x2 , . . . , xn )T = 0 0 < Q(1) (x(1) ) !

A(1) " # $

% & A(1) " # $ ' x = 0 Q(x) ≥ 0 & Q(x) = 0 '

! # ! ( Q(1) (x(1) ) = 0 ) x2 = x3 = . . . = xn = 0 '

# ! l11 = 0 x1 = 0 * + , A " # $ ( ' (

" ! - # . /

! " # $ '. #

A = (aik ) ∈ Rn,n

!" #$ %

& % 0 A " # $ a11 > 0 1# * * + , A(1) ! ' (1) " # $ a22 > 0 2

1# * (n−1) + A(k) k = 2, 3, . . . , n − 1 ! ann 1# " # (1)

(n−1)

' 1# a11 > 0, a22 > 0, . . . , ann > 0 + , (n−1) A(n−1) = (ann ) " # $

# 23 ( # ' ! + A(n−2) , . . . , A(1) , A " # $ 4 ! ' 5 6

.

! " # $ + A *! 7 3/( 8 # ! ! * ! 9 + 7 !

. .

! :!" , : :! 8 ;2

A = (aik ) ∈ Rn,n ' ( ) Q(x) * n + n 2 n n n Q(x) = aik xi xk = lik xi ! ! &2 9 73 2 k / :

!

lkk (k)

aij

% (k−1) = akk ; (k−1)

= aij

(k−1)

lik =

− lik ljk ,

aik , lkk

i = k + 1, k + 2, . . . , n,

i, j = k + 1, k + 2, . . . , n.

A

! "#$% lik & # '# i ≥ k '# &# # &# (#)#* ⎞ ⎛ l11 0 0 ... 0 ⎜ l21 l22 0 ... 0 ⎟ ⎟ ⎜ ⎜ l31 l32 l33 . . . 0 ⎟ L=⎜ + ⎟ ⎟ ⎜

⎠ ⎝

ln1

ln2

ln3

. . . lnn

!" " !"#" $% A

,

A = LLT .

&' - . / 0# 1#) Q(x) & # # ) # (#)#* L + Q(x) = xT Ax = (LT x)T (LT x) = xT LLT x.

2 # 3 # # ,

! , ( )*+" " # 4))# !#* A

"5 ( ) 67 .8 #'

! 9 # :4; m.

()*+,

# m %

L A = LL

!" # m $ lik = 0 %& i k i − k > m. ()*-, T

' .& (/, (/0, 1 L m (1)

% A(1) = (aik ) # m # 2 (/, li1 = 0 i i − 1 > m 3 ai1 = 0 (1) # 1! aik 1 (i, k) i ≥ k ≥ 2 i − k > m 3 aik = 0 4 li1 = 0 i − 1 > i − k > m (/0, 5 (1) aik = 0 i, k ≥ 2 |i − k| > m 1 * 6 7&!8' ! " #8 % 6 m % L 9 5 % A & ' & : .& # & # ; m ' ' 3 ) .& # % m = 4 . .& 6 × 4 1 * + 5 D( , -B $ n = 20 000 n = 35 000 ! D( E D( ( ( ( ! # F $ 6 $ 3 ,( % .( && .( % 3 . ' $!

# 5 B1 (& F 5 & & '( , 1 - ' G '( "! & . 3 3 ( &(1 H $ 6 0 ( 34 ( 34 $ ! ) 3 I( ( ( b (n + 1)1 n × (n + 1)1, - A 33 $ 6 ( & n

aik xk = ai,n+1 ,

i = 1, 2, . . . , n,

k=1

! # C '( 3 "!> (( ( 34 (n − 1) , -& '( A6 $ & & ( .'(& 1 a11 & ! # / $ '( ( 3 h = 1/a11 34 i = 2, 3, . . . , n :

li1 = h × ai1 .

"!" , 2 , & . ** ?*

! " #

$ % & '! # ( )*!++, - ./0 1 20 )*!++3, )*!++4, # 2 $ )*!++, mi+1 mi / ! 2 - 2 ! 5 .2 6 2 - $ 78 94:! 0 a1 x1 ci xi−1

+ +

b1 x2 ai xi cn xn−1

+ bi xi+1 + an xn

= d1 , = di , = dn .

i = 2, 3, . . . , n − 1,

)*!+,

; ) R 9 * ) : &" ?+7 y y1 = d1 i = 2, 3, . . . , m − 1 : yi = di − ri × yi−1

yn = dn i = n − 1, n − 2, . . . , m + 1 : yi = di − ri+1 × yi+1

# m* ;" rm ym−1 + ym + rm+1 ym+1 = dm

+ &"7

) ' ym−1 ym+1 ym = dm − rm × ym−1 − rm−1 × ym+1 .

1

) ;@*#" + )* 9

*

: &" , ) xi " , ) xm " + + > !

" >; + 4 * - 1 - 1 & ! 1 2 n = 8 $ + , & + ?

x1 a1

x3

x5

x7

a3

x2 b1 c3

a5

x4 b3 c5

a7 c2

b2 c4

x6

x8

b5 c7

b7

a2 b4 c6

a4 b6 c8

a6 a8

1 d1 d3 d5 d7 d2 d4 d6 d8

8=!@=;

6 A P ∈ Rn,n + , Ax = d ( P AP T (P x) = P d 6 A P AP T # P AP

T

=

A1 C

B A2

$

8=!@>;

& A1 , A2 ∈ Rm,m - " B C

(m × m) ⎛ ⎛ ⎞ ⎞ x1 x2 ⎜ x3 ⎜ x4 ⎟ ⎟ ⎜ ⎜ ⎟ ⎟ y 1 := ⎜ ⎟ , y 2 := ⎜ ⎟ , ⎝ ⎝ ⎠ ⎠ xn−1 d1 d3

⎛ ⎜ ⎜ v 1 := ⎜ ⎝

⎛

⎞

⎜ ⎟ ⎜ ⎟ ⎟ , v 2 := ⎜ ⎝ ⎠

dn−1

xn d2 d4

⎞

⎟ ⎟ ⎟ ∈ Rm ⎠

dn

!" # A1 y 1 + B y 2

=

v1 ,

C y 1 + A2 y 2

=

v2 .

$

%& '" ( ) A A1 # A2 # *" # # $ + −1 y 1 = A−1 1 v 1 − A1 B y 2 ,

−1 y 2 = A−1 2 v 2 − A2 C y 1 .

,

- y 2 # , # y 1 # , $ # −1 (A1 − B A−1 2 C)y 1 = (v 1 − B A2 v 2 ),

(A2 − C

A−1 1 B)y 2

= (v 2 − C

A−1 1 v 1 ).

.

/ # ' +& m 0! x1 , x3 , . . . , xn−1 " # . +& m 0! x2 , x4 , . . . , xn 1 A1 := A1 − B A−1 2 C,

A2 := A2 − C A−1 1 B

(1)

(1)

$

" 2#! # # 1 / # ' 3 n/2 0 ! !4 # * ( - #+ 2 4 " 5 # 1 67# ⎞ ⎛ (1) (1) a1 b1 (1) (1) ⎟ ⎜ (1) a3 b3 ⎟ ⎜ c3 ⎟ ⎜ (1) (1) (1) (1) ⎟, c a b A1 := ⎜ 5 5 5 ⎟ ⎜ ⎟ ⎜ ⎝ ⎠ (1)

⎛ (1)

d1

⎜ ⎜ ⎜ ⎜ := v 1 − BA−1 v = 2 2 ⎜ ⎜ ⎝

cn−1 (1)

d1 (1) d3 (1) d5

(1)

⎞

an−1

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠

(1)

dn−1 (1)

(1)

# +& A2 # d2 89 #

(1)

(1)

A1 y 1 = d1 ,

(1)

(1)

A2 y 2 = d2 .

(1) A1

(1) d1

⎫ (1) ⎪ ai = ai − bi−1 ci /ai−1 − bi ci+1 /ai+1 ⎪ ⎪ ⎪ ⎬ (1) (1) bi = −bi bi+1 /ai+1 , ci = −ci−1 ci /ai−1 i = 1, 3, . . . , n − 1, ⎪ ⎪ ⎪ ⎪ (1) ⎭ di = di − di−1 ci /ai−1 − bi di+1 /ai+1

! "#" $ a0 = 1% b0 = bn = c0 = c1 = d0 = 0 ! & ' (% ) !* ") + * % ! ) $ an+1 = 1, bn+1 = cn+1 = dn+1 = 0 ) $ , - %

. / 0" + !* 1 ) # 2 ! ") 3 " !* ) 4

! $ ' ") 5 2 ! ) % ,!

! ) ) % ) 3 5 2 ) ,!2 " 6 5 2 " 22 )% 2 3 "2

, - . Ax = d

(1)

(1)

(1)

(2)

(2)

A 1 z 1 = d1

(2)

(1)

A 2 y 2 = d2

A 1 y 1 = d1

(2)

A 2 z 2 = d2

(2)

(2)

A 3 z 3 = d3

(2)

(2)

A 4 z 4 = d4

+ * 22 74 5 %

5 4 ! 8 " 4 " " " 1 2 " n = 2p , p ∈ N∗ %

22 p ! " ) % + ' !* 8

* % 9 8

: !) ;2

# (4np − 4n + 4) , % (6np − 8n + 8) 2 (2np − n + 2) &* ;? ?

3 )

! ! "# $%& ' & ( )*& ( )+,& - & . /0 1 2 3 - & 4 ( # - p - &

5 "6 %,

7 A ! 1 p / #

8 1 9 5 / 8

5 : ( 7 1 / - 1 - & 8 0 3; ; - ), 6; "' $%, - 1 ? @ "# $%,

0- A 2 3 - p % 7 p

(p) Pn (x) # & $ x 2 % 8 1 f (x) 4 , 1 6 % 0 9:; ? $ $#

1 P2 (x) $ # (x0 , y0 ), (x2 , y2 ) $ # $ @ A

$ #

(x1 , y1 )

! "

#

$% &

"" ' " " $ (

) " & * + & ," "

1 [−11y0 + 18y1 − 9y2 + 2y3 ] 6h 1 [−2y0 − 3y1 + 6y2 − y3 ] f (x1 ) ≈ 6h 1 [y0 − 27y1 + 27y2 − y3 ] f (xM ) ≈ 24h 1 f (xM ) ≈ 2 [y0 − y1 − y2 + y3 ] 2h 1 xM = (x0 + x3 ) 2 f (x0 ) ≈

f (x) = sinh(x) x = 0.6 !

" # $%&' ( ) * h $ + * )

" ! $ , - . h, x0 , x2 , y0 , y2 /- ( f (0.6) = sinh(0.6) = 0.636653582 $ h

x0

x2

y0

y2

f (x1 ) ≈

0.1 0.01 0.001 0.0001 0.00001

0.50 0.59 0.599 0.5999 0.59999

0.7 0.61 0.601 0.6001 0.60001

0.521095305 0.624830565 0.635468435 0.636535039 0.636641728

0.758583702 0.648540265 0.637839366 0.636772132 0.636665437

0.637184300 0.636660000 0.637000000 0.700000000 10.00000000

0 h 1 ( h = 0.00001 /- $

"

" + . + % $ & '

& / " &

0 , + 1" 2 0 $"" $ 3 4 & & 1" . %

" ) , " 0 & , $

f (x) p4 "

+

" 5

$"" ( 0 $ 0 6) 4* & $

y1 = f (x1 ) = f (x0 + h) !" #$ h2 h3 h4 f (x0 ) + f (3) (x0 ) + f (4) (x0 ) + . . . 2! 3! 4! % ! y0 = f (x0 ) y1 = f (x0 ) + hf (x0 ) +

y1 − y0 h h2 h3 = f (x0 ) + f (x0 ) + f (3) (x0 ) + f (4) (x0 ) + . . . h 2! 3! 4! % f (x0 ) ! & % !% ' h !%% (%% & ! ) ! !" # $ y2

y0

=

f (x2 ) = f (x1 + h)

=

f (x1 ) + hf (x1 ) +

=

f (x0 ) = f (x1 − h)

h2 h3 h4 f (x1 ) + f (3) (x1 ) + f (4) (x1 ) + + . . . 2! 3! 4!

h2 h3 h4 f (x1 ) − f (3) (x1 ) + f (4) (x1 ) − + . . . 2! 3! 4! 2 4 6 h h h 1 [y2 − y0 ] = f (x1 ) + f (3) (x1 ) + f (5) (x1 ) + f (7) (x1 ) + . . . 2h 3! 5! 7! ! ) ! * % +, f (x1 ) & % ' ! h - (%%

! & % . ( &

% . % +// 0! %

% ! % % - =

f (x1 ) − hf (x1 ) +

% ! !% $% ! 2h2 (4) 2h4 (6) 2h6 (8) y2 − 2y1 + y0 = f (x1 ) + f (x1 ) + f (x1 ) + f (x1 ) + . . . 2 h 4! 6! 8! 1 ,%% % %! !%% B(t) . '! ! t !,( A +, % !// 0 & % !% ' t ! % % !%% % 23 a1 , a2 , . . . B(t) = A + a1 t + a2 t2 + a3 t3 + . . . + an tn + . . .

4

+% % 5 !, !% 5 % + ! % % % 6 , ,! 5 67 B(t) % - '! ! t ,% !%% B(t) +// 0! A ! % !% ,%

! '! ! t0 > t1 > t2 > . . . > tn > 0 * B(tk ) , ! 6 8 /! %/" Pk (t) %-%%. ! !7 !,

9 % 9 t = 0 !% : k % * Pk (0) ,%% ;( % % * B(0) = A ! 10 !/!

!,, %,! 0 !/ * Pk (0) % * A

. , 5!- ! % % 10 !/! %/ %%% -! ; #8 /!

f (x) = sinh(x) x = 0.6

! " # t = h2 B(tk ) := [y2 − 2y1 + y0 ]/tk $ % &' & & (

) yi = sinh(xi ) & ) % *$ $ + , Pk (0) - % , . hk

tk = h2k

0.30 0.20 0.15 0.10

0.09 0.04 0.0225 0.01

*$ &/ tk B(tk ) 0.6414428889 0.6387786000 0.6378482222 0.6371843000

0.05328577800 0.05316444571 0.05311377600

0.001797515344 0.001688990476

0.001356560849

0 12 cj ' j = 0, 1, 2, 3' # 3 Pk (t)' k = 0, 1, 2, 3 f (0.6) = sinh(0.6) = 0.6366535821482413 k

1

2

3

Pk (0) |Pk (0) − sinh(0)|

0.6366471689 6.4133 · 10−6

0.6366536399 5.7787 · 10−8

0.6366535300 5.2094 · 10−8

Pk (0) *0 B(tk ) P3 (0) , y $

! " ! ! # $ "! ! %" ! & & ' ( ! ! ! ) "! ! " ! * " + ,-. / & 0 $ ! ! 1 ! $ ( ) $ ! ! ! 2 3 . " 4 ! !5$ 6 " ! %" ! ! $ 2 & 7 ! *!8 • 2 ! " ) +9 ! k • 2 ! p !5 • ! $ ! ! ! *! ! : $ ! ! ,

/ ; 0 ∀t ∈ (0, 1).

t

= i/n

!"# !"# !"# !"#

//% / % /% /"%

Bin [0, 1] !" #

$% Bin (t) B0n (t)

= t Bi−1,n−1 (t) + (1 − t) Bi,n−1 (t), = (1 − t) B0,n−1 (t),

Bnn (t)

= t Bn−1,n−1 (t).

i = 1, . . . , n − 1,

!"# /3%

{Bin (t)}ni=0 Πn n (n ≥ 1) ⎧ ⎨ −n B0,n−1 (t) Bin (t) = n [Bi−1,n−1 (t) − Bi,n−1 (t)] ⎩ n Bn−1,n−1 (t)

i = 0, i = 1, 2, . . . , n − 1, i = n.

Πn ! p ∈ Πn n p(t) = βi Bin (t). " i=0

%

¿ # p

βi

$

(i/n, βi )T ∈ R2 , i = 0, 1, . . . , n,

!

& ' () % * $

p(t) 1

0.5

t

0 0

1/3

2/3

1

−0.5

−1

(2/3, −1) (1, 1)

(0, 0) (1/3, −1)

p(t) = 0 · B03 (t) − B13 (t) − B23 (t) + B33 (t) = t3 + 3t2 − 3t

¿

! t = 0 t = 1 " # $ %& βi ' n−k p(k) (t) = n(n − 1) · · · (n − k + 1) Δk βi Bi,n−k (t), i=0

( Δk )(* + Δβi := βi+1 − βi , Δk βi := Δk−1 βi+1 − Δk−1 βi

! β0 (1 − t)B0,n−1 (t) + β1 [(1 − t)B1,n−1 (t) + tB0,n−1 (t)] + · · · · · · + βn tBn−1,n−1 (t)

p(t) =

[β0 (1 − t) + β1 t]B0,n−1 (t) + · · · + [βn−1 (1 − t) + βn t]Bn−1,n−1 (t),

=

" p(t)

n−1

=

(1)

βi

Bi,n−1 (t)

i=0 (1)

βi

= βi (1 − t) + βi+1 t, i = 0, . . . , n − 1,

(1)

βi

(1)

= βi (t).

# " $" % & " (n)

'

p(t) = β0 .

% ! ( ) p(t) * ! $ ! ! " β0

=

(0)

β0

(1)

β0

(1)

βn

=

(0)

·

··

(n)

β0

βn−1

βn

$ + $ , - (1)

, - βi $ .( % $ /" 0" 1 ( $ ( !

$

( (xi , yi ) i+1 i+t i = xi = (1 − t) + t n n n 2 (1) βi = yi = (1 − t)βi + tβi+1 , i = 0, . . . , n − 1 ( " $ 3 "$ # $ # $ i/n (i + 1)/n → , βi βi+1

(k)

βi k = 1, . . . , n i = 0, . . . , n − k (k−1) (n) ! βi

" p(t) = β0 # ! $ %

t = 0.5 p(t) = 0 · B03 (t) − B13 (t) − B23 (t) + B33 (t) !! " # $"" !% & &' " ( )$ * t = 0.5 $ & (0, 0)' (1/3, −1)' (2/3, −1)' (1, 1) * t = 0.5 + & (1) (xi , βi ) , * * -◦. / " 0 ' & " ' * * -+. / + & " " 1" *& -•. * & p(0.5)

p(t) 1

0.5

t

0 1/3

2/3

1

−0.5

−1

$"" !% / ( )$ * *

! # " &' ( ) ( "' # " * ( # +" ( *" ,

% t- % " +" ! ! ." /

* 0 ≤ t ≤ 1 ) xk (t) k = 1, 2, . . . , d # (x1 (t), x2 (t), . . . , xd (t))T Rd

0 % d = 2 " ' ( P (t) = (x(t), y(t))T " ( % 1 2. % ( 2 *"

# $ xi ∈ R2 , yi x

Pi =

P 0 , . . . , P n ∈ R2 n + 1

# $ n x(t) = P (t) = Bin (t)P i . y(t) i=0

x(t) y(t)

!" #" $ % #" ! & ! ' n = 3 ( " # $ xi ∈ R2 , i = 0, 1, 2, 3. P i0 := P i = yi

) ) "& ' ' t '" ! & * P i1 P i2

:= (1 − t) P i0 + t P i+1,0 , i = 0, 1, 2 := (1 − t) P i1 + t P i+1,1 , i = 0, 1

P 03

:= (1 − t) P 02 + t P 12 .

P 03

= (1 − t) P 02 + t P 12

" = (1 − t)((1 − t) P 01 + t P 11 ) + t((1 − t) P 11 + t P 21 ) = (1 − t)3 P 00 + 3(1 − t)2 tP 10 + 3(1 − t)t2 P 20 + t3 P 30

+ , ' !" -" " - # ' t = 1/2 && +! ' " . "

% ' , +! ' - # ! " ) (" '" ! ( /

M :=

P (t) =

n

Bin (t)P i , t ∈ [0, 1]

i=0

n + 1 P 0 P 1 . . . P n

0 ( '" !

! "

P (t) =

.n

P (0) = P 0 ,

P (1) = P n ,

P (0) = n (P 1 − P 0 ),

P (1) = n (P n − P n−1 ).

i=0

Bin (t)P i n ≥ 2 #

/ 1

P 1 = P 10

3

P 11 2.5

P 2 = P 20 P 12

P 02

2

P 03 = P (t) P 01

1.5

P 21

1

P 3 = P 30 0.5

0

P 0 = P 00 0

1

0.5

1.5

2

! "# t = 1/2

P (t)

n ∗∗ !

# $ x(t) P (t) = 0 ≤ t ≤ 1 n y(t)

⎛ P (t) = (P 0 P 1 . . . P n ) B n

⎞ tn ⎜ tn−1 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ t ⎠ 1

"!

#$

"!

%$

n B n n + 1 bi+1,k+1

# $# $ ⎧ ⎨ (−1)i+k+n n − i n = k i ⎩ 0

!

i = 0, 1, . . . , n, k = 0, 1, . . . n − i

P 3 (t) =

! x(t) = y(t)

! x0 y0

x1 y1

x2 y2

x3 y3

0 B B B @

−1 3 −3 1

3 −6 3 0

−3 3 0 0

1 0 0 0

10 CB CB CB A@

t3 t2 t 1

1 C C C. A

! " # $

$

" # # %

# ! $ &

"

' " & $ # !!

( ! ) $ ! * $ '# ( ( ( # '# &

% ! ' $ ( $ "# " $" ! + ,& & ,& " ! ( u " m $ " -

( % n ! ( u0 < u1 < u2 < u3 < . . . um−1 < um ,

j # n P j (u) = P ij Bin (u; uj−1 , uj ), u ∈ [uj−1 , uj ],

.!

*/

.!

0/

i=0

( P 0j P 1j , . . . , P nj j = 1, 2, . . . , m! ,& j (

[uj−1 , uj ] hj := uj − uj−1 ! j (j + 1)

$ u = uj

.! 12/

P n,j = P 0,j+1 P j (uj )

! 3 u = uj # C 1 $

= 4 .!00/ '# ( - # $ d u − uj−1 d d 1 Bin (u; uj−1 , uj ) = Bin = Bin (t) · , du du uj − uj−1 dt hj

P j+1 (uj )

!

.! 5/ n(P n,j − P n−1,j )/hj = n(P 1,j+1 − P 0,j+1 )/hj+1 .

.! 1 /

4 $ P n,j = P 0,j+1

.! 1 / C 1 $ u = uj 6 P n,j =

hj+1 hj P n−1,j + P 1,j+1 hj + hj+1 hj + hj+1

.! 11/

j (j + 1) P n,j = P 0,j+1 P n−1,j P 1,j+1 ! ""#$ % P n−1,j P 1,j+1 P n,j &' hj : hj+1 ( ' )* + , +- ) + + . '/ 0) $ m n $ + m·n+1 $ d & 1 2 3 3 % ! "4# ) 5 $ + d ( m·n+1 %6 6 ! "#

B := (P 0 , P 1 , P 2 , P 3 , P 4 , . . . , P m·n−1 , P m·n )

j ) + uj ! 7# n P j (u) = P (j−1)·n+i Bin (u; uj−1 , uj ), j = 1, 2, . . . , m. ! "8# i=0

0)* %6 B ' C p % p ≥ 1$ * 6 u p , + % 9 + $ + '/ : u + + + 3 $ ! "8# ) ; n P j (t) = P (j−1)·n+i Bin (t), t ∈ [0, 1], j = 1, 2, . . . , m. ! "# i=0

+ +$ + <

r = 1 !!" # $ $% & $ ! & $ '( ) *$ P 1

P 2 ( + & $ +$ $% ,$' ( + + ξ ( - .(( /01 ) . +' $ ! ! 3 X 1 1 3 (1 − t) + 3t(1 − t)2 + P (t) = P i Bi3 (t) = 0 ξ i=0

! ξ 1

! 2

3t (1 − t) +

0 1

t3 .

2 $ ξ + # (! #% P (0.5) + $ ) + 3 ξ = 0.552285 ) .(( /0 $ # " 0.00027 ( +' 2# $ 4 $ . 5 $ ! 6 ( a = 1/ξ = 1.81066 b = 1

+ $ , 0 ( $ C 1 ,$

y

„ P3 =

1

0 1

«

„ P2 =

ξ 1

«

„ P1 =

„ P0 = 1

0

1 ξ

1 0

«

«

x

!" #$

%" & B=

a 0

a ξ

1 1

0 1

−1 1

−a ξ

−a 0

−a −ξ

−1 −1

! 0 −1

1 −1

a −ξ

a 0

' () * $+$ , !" - !" !" !" $ C 1 #$ !" $ ' !" !" $ #$

. $ $ ( !"/ C 1 #$ !" ' ( 0 1 $ u0 = 0/ u1 = 1.6/ u2 = 2.6/ u3 = 3.1/ u4 = 3.6/ u5 = 4.6/ u6 = 6.2 $ $ - $ !" #$ " ( 2$ %$ & $"3$

) !" - $ 4!"- * $$ / 5 1 4!" )

! "#

$ % &'( ) * + , $ * * -** '! ./* S & )** *" 0 & 1 *2 * + * * * % 0 *& 3 ' * 42 !**

! "#$ % "#& $ ! # & # s t$ ! # '

$ # u v % &# ( )

$ # ! # & $ ! & # & m # # "# *& # & "#! ! # n & $ + # "# & & % "#&$ , " - # &

m n x(s, t) := P ij Bin (s)Bjm (t), s, t ∈ [0, 1]. i=0 j=0

P ij i = 0, 1, . . . , n! j = 0, 1, . . . , m " # x(s, t) $ % (n + 1)(m + 1) &' ()* P ij &' ()* + ⎛ ⎞ P 00 P 01 . . . P 0m ⎜ P 10 P 11 . . . P 1m ⎟ ⎜ ⎟ , ⎜ ⎟ ⎝ ⎠ P n0

P n1

. . . P nm

* - P ij ∈ R3 %. * /+ k = 1, 2, 3 * - * 0 # 11 * 1

x(0, 0) = P 00 , x(0, t) =

m

x(s, t)

x(0, 1) = P 0m ,

P 0j Bjm (t),

x(1, 0) = P n0 ,

x(1, t) =

j=0

x(s, 0) =

n

m

x(1, 1) = P nm ,

P nj Bjm (t),

2

P im Bin (s).

1

j=0

P i0 Bin (s),

i=0

x(s, 1) =

n i=0

3 * &' ()* P 00 , P 0m , P n0 * P nm - &' (04. x(s, t) # * 2 * 1 5 04 x(s, t) 6 *# &' ("*# 7 &' ()* + , &' ()* 6 ( *# 2 * * 8 # , &' ()* 6 *# 1 *% 3* 0* 7* # 04 %

M := {x(s, t)|s, t ∈ [0, 1]}

! "#" 9 8 . * &(): %. * m n−1 ∂x =n (P i+1,j − P i,j )Bi,n−1 (s)Bjm (t), ∂s i=0 j=0

n m−1 ∂x =m (P i,j+1 − P i,j )Bin (s)Bj,m−1 (t), ∂t i=0 j=0

!

x(s, t)

m ∂x(0, t) =n (P 1j − P 0j )Bjm (t), ∂s j=0 m ∂x(1, t) =n (P n,j − P n−1,j )Bjm (t), ∂s j=0

n ∂x(s, 0) =m (P i1 − P i0 )Bin (s), ∂t i=0 n ∂x(s, 1) =m (P i,m − P i,m−1 )Bin (s). ∂t i=0

!

" # $ % & x(s, t) ' ' ( ) "

* %+ , s = n m m x(s, t) = P ij Bin (s) Bjm (t) =: Qj (s)Bjm (t) j=0

i=0

j=0

%+ ,- (m + 1) s %+ ,./ n Qj (s) := P ij Bin (s), j = 0, 1, . . . , m.

0

i=0

- ' ( ) & s (m + 1) " %+ ,./ 1

2 3 4/ Qj (s) / ) t '

( ) ' % * x(s, t) t = 5

' ( ) (n+1) %+ ,./ 1 %+ ,./ / t =

5 × 4 ! " # $

1 10 10 0 0.0 0.9 0.7 0.0 0.0 0.0 0.0 0.0 0.0 0.333 0.666 1.0 B 0.0 0.333 0.666 1.0 C B 0.25 0.25 0.25 0.25 C B 1.0 2.4 2.2 1.0 C C CB CB B C CB CB B 0.5 0.5 0.5 C B 2.2 3.4 3.1 2.1 C . B 0.0 0.333 0.666 1.0 C B 0.5 C CB CB B @ 0.0 0.333 0.666 1.0 A @ 0.75 0.75 0.75 0.75 A @ 1.9 2.9 2.7 1.9 A 1.7 2.4 2.3 1.8 1.0 1.0 1.0 1.0 0.0 0.333 0.666 1.0

! " # $% s = 0, 1/15, 2/15, . . . , 1.0 & $% t = 0, 1/11, 2/11, . . . , 1.0 !" ' # ( ) & " $% % * " + # , & " "

!" 5 × 4

! " # $ C 1 % # & $

'

! ( ) * $ ( + ,' - ..' /' 0' ( ..' /1' /' " /23!

! +4' 560# .22, 7

899: ' ;' ! ! (

' ; ' ! ! ;' ! 0 (a, b) ' ) %&(

% (a, b) * & + & f (a, b) & w ,- αi , i = 0, 1, . . . , n g(x) := g(x; α0 , α1 , . . . , αn ) :=

n

"# .$

αi ϕi (x),

i=0

)

b

(f (x) − g(x))2 w(x) dx → min .

F (α0 , α1 , . . . , αn ) := a

αi

"# /$

01 & 01 & 2'! "# #3$ ) & 4 5 ,- 2'! & ) b (ϕi , ϕj ) := ϕi (x) ϕj (x)w(x) dx "# 3$ a

) b (f, ϕj ) := f (x) ϕj (x)w(x) dx.

a

!! " # $ $ % $ & $% ' () # " * $ +

# ,- .# ,/ -

(ϕi , ϕj ) = 0, $ i = j.

0

12 .# # αi =

(f, ϕi ) , i = 0, 1, . . . , n. (ϕi , ϕi )

3

4 -

2+&!! " # # 5.# # # ,- 6 -

ϕj (x) := xj ,

x ∈ [0, 1],

j = 0, 1, . . . , n,

w(x) ≡ 1 !" #

Z Z 1

1

ϕi (x) ϕj (x)w(x) dx =

$ #

0

0

xi+j dx =

1 . i+j+1

% &# '(( #

f : R → R 2π f (x + 2π) = f (x) x ∈ R. −f (x) ! x0 " y0 y0+ lim f (x0 − h) = y0− , lim f (x0 + h) = y0+ # h→+0 h→+0 $ % f (x) % & (2π)' % % 1, cos(x), sin(x), cos(2x), sin(2x), . . . , cos(nx), sin(nx)

1 a0 + {ak cos(kx) + bk sin(kx)} 2 n

gn (x) =

k=1

⎧ π ⎫1/2 ⎨) ⎬ gn (x) − f (x)2 := {gn (x) − f (x)}2 dx → min ⎩ ⎭

−π

(

! "# $ %&'

[−π, π] ! "# $ %& )π −π

⎧ ⎨ 0 cos(jx) cos(kx) dx = 2π ⎩ π !

)π sin(jx) sin(kx) dx =

j = k j = k = 0 j = k > 0 j = k, j, k > 0 j = k > 0

0 π

−π

)

)π cos(jx) sin(kx) dx = 0

j ≥ 0, k > 0

*

−π

%# ( % + $ ,-

)π −π

1 cos(jx) cos(kx) dx = 2

)π [cos{(j + k)x} + cos{(j − k)x}] dx. −π

/ j = k ' (π 1 1 1 sin{(j + k)x} + sin{(j − k)x} =0 2 j+k j−k −π

0 / j = k > 0 . ' (π 1 1 sin{(j + k)x} + x =π 2 j+k −π

.

! " # $ )π

1 sin(jx) sin(kx) dx = − 2

−π

)π [cos{(j + k)x} − cos{(j − k)x}] dx, −π

% & ' " $ ( ) ) $ ' * + % ( , ' ) + ' "- $ . 2π - ++ ' $ [a, b] "- & " t = 2π (x − a)/(b − a)

" ) / 1, cos(kt), sin(kt), . . . 0 * 1#2 .! 3 4 αi = (f, ϕi )/(ϕi , ϕi ) 5 + + % " #

' 1 ' 3 4 1 ak = π 1 bk = π

)π f (x) cos(kx) dx,

k = 0, 1, . . . , n,

−π )π

5 f (x) sin(kx) dx,

k = 1, 2, . . . , n.

−π

2 6 (2π),7 ' ) f (x) + ) gn (x) ,3 4 ! ,( / )! "- ++ 6 n 8 9 (2π),7 ' -') ) f (x) ' #-+ '

g(x) :=

∞

1 a0 + {ak cos(kx) + bk sin(kx)} 2

k=1

" + ) * :; %

f (x) (2π) ! " # g(x) $%&'&( !( ) f (x0 ) *! f (x) ! + x0 1

( {y0− + y0+ } , $%&-.( *! f (x) ! + x0 + 2 ? 2 @ '6 ' -') 1 ) # 7 ) & " +7 f (x) = |x| "- x = 0

y

x −π

π

0

2π

g3 (x)

(2π) f (x) [−π, π] f (x) = |x|,

−π ≤ x ≤ π.

! "#$

% & &' ( ) !' $ % ' * '

* +,) bk = 0 - . ' ak ( & Zπ Zπ 1 2 a0 = |x| dx = x dx = π π π −π 0 3 2 ˛π Zπ Zπ ˛ 2 2 41 1 ˛ x cos(kx) dx = sin(kx) dx5 x sin(kx)˛ − ak = ˛ π π k k 0 0 0 ˛π ˛ 2 2 ˛ = cos(kx)˛ = [(−1)k − 1], k > 0 ˛ πk2 πk2 0

) '/' 0 ﬀ j 1 cos(3x) cos(5x) 4 cos(x) g(x) = π − + + + . . . . 2 π 12 32 52

! "# $

g3 (x) ') 1 f (x) ' f 2 ) ' % ) # (3 * ' % ) # g(0) = 0 ' 1 1 1 1 π2 = 2 + 2 + 2 + 2 + ... 8 1 3 5 7

(2π) f (x) (0, 2π) 2

f (x) = x ,

0 < x < 2π.

! "#4$

% ) (3 xk = 2πk, (k ∈ Z) % ' * (3 2 ) ' % ) # ) '/' +,) 5 6 ( ' 1 a0 = π

Z2π 0

x2 dx =

8π 2 3

y 4π 2

f (x)

2π 2

g4 (x)

x −π

π

0

2π

1 π

ak =

1 bk = π

Z2π

x2 cos(kx) dx =

0

Z2π

4 , k2

x2 sin(kx) dx = −

0

4π , k

k = 1, 2, . . .

k = 1, 2, . . .

ﬀ ∞ j 4π 2 X 4 4π g(x) = cos(kx) − + sin(kx) . 3 k2 k k=1

!"#$

% & % ' f (x) ( g4 (x) ) ' * + ' & , -

ak bk ! " # $ # $% $

& %' & ( ( ( ) * ++ , ( - + " . ( / ( 0 1! )

( [0, 2π] N 2 ( & 3 $ h xj h=

2π , N

xj = hj =

2π j, N

j = 0, 1, 2, . . . , N

& $

2 + 1 ! ak

=

1 π

)2π f (x) cos(kx) dx 0

!

≈

⎫ ⎧ N −1 ⎬ 1 2π ⎨ f (xj ) cos(kxj ) + f (xN ) cos(kxN ) . f (x0 ) cos(kx0 ) + 2 ⎭ π 2N ⎩ j=1

(2π) f (x) cos(kx) ak bk a∗k

N 2 := f (xj ) cos(kxj ), N j=1

b∗k

N 2 := f (xj ) sin(kxj ), N j=1

k = 0, 1, 2, . . . ,

! "#$ k = 1, 2, 3, . . . .

%&' ' () a∗k b∗k *

+ ! , - . ! "$ ! /$ 0 ' % !

xj

N

!

cos(kxj ) =

j=1 N

sin(kxj ) = 0

0 N

k/N ∈/ Z

k/N ∈ Z

! "/$

k ∈ Z.

! "1$

j=1

2 '34 5''

S :=

N N N {cos(kxj ) + i sin(kxj )} = eikxj = eijkh , j=1

j=1

! #$

j=1

' 6 ' ' '34$ 7 q := eikh = e2πik/N

! * %

. ' 2

''! 8

k/N ∈ / Z

q = 1 5''' S = eikh

eikhN − 1 e2πki − 1 = eikh ikh = 0, ikh e −1 e −1

k/N ∈ / Z.

8

k/N ∈ Z q = 1

S = N

! , *

' 6 ' 8' S ! #$ 3 ! "/$ ! "1$!

xj ! ⎧ k+l k−l ⎪ ⎪ 0, ∈ / Z ∈ /Z

⎪ ⎪ N N ⎪ N

⎪ ⎨

k+l k−l ∈ Z ∈ Z N N j=1 k N+ l ∈ Z k N− l ∈ Z k N+ l ∈/ Z k N− l ∈/ Z N k N+ l ∈ Z k N− l ∈ Z sin(kxj ) sin(lxj ) = ⎪ ⎪ N k+l k−l j=1 ⎪ ⎪ ∈ Z ∈ /Z − ,

⎪ ⎪ 2 N N ⎪ ⎪ ⎪ ⎩ N, k N+ l ∈/ Z k N− l ∈ Z 2 N cos(kxj ) sin(lxj ) = 0, k, l ∈ N cos(kxj ) cos(lxj ) =

N , ⎪ 2 ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ N, ⎧ ⎪ ⎪ 0, ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨

"

j=1

#"

! "

cos(kxj ) cos(lxj ) =

1 [cos{(k + l)xj } + cos{(k − l)xj }] 2

sin(kxj ) sin(lxj ) =

1 [cos{(k − l)xj } − cos{(k + l)xj }] 2

cos(kxj ) sin(lxj ) =

1 [sin{(k + l)xj } − sin{(k − l)xj }] 2

# $ %& & ' ( & ) & * + ! ", -& ak bk . & * & ! * / 0 a∗k b∗k 1 ' / * %*" (f, ϕj ) 2 ϕ2k (x) = cos(kx) )&' ϕ2k+1 (x) = sin(kx)( k = 0, 1, 2, . . .(

' ' %& 3 & 4* #&" %* ) ( . & * 5) $ * & " #6 ) ( ) * 4* 5) #67 * ) ' ! ", -& a∗k b∗k ) * %& * #

y 4π 2

f (x)

g3∗ (x)

2π 2

x −π

π

0

2π

N ∗ gm (x) :=

= 2n, n ∈ N∗

1 ∗ a + 2 0

m

{a∗k cos(kx) + b∗k sin(kx)}

k=1

m < n ! f (x) ! " #$ % N &' xj ( & ) *+,#$ - F :=

N

∗ {gm (xj ) − f (xj )}2

j=1

(2π) f (x) = x2 , 0 < x < 2π! "

# f (0) = f (2π) = 2π 2 ! N = 12 $% . . . . 4.092652, a∗2 = 1.096623, a∗3 = 0.548311, a∗0 = 26.410330, a∗1 = . . . b∗1 = −12.277955, b∗2 = −5.698219, b∗3 = −3.289868. & ' ( ) g3∗ (x) f (x)

m ! " # $ % & '$ ()% *+

N gn∗ (x) :=

= 2n, n ∈ N∗

1 ∗ a + 2 0

n−1 k=1

1 {a∗k cos(kx) + b∗k sin(kx)} + a∗n cos(nx) 2

,

-( &' xj &' f (xj )( j = 1, 2, . . . , N

y π

x x1

0

x2

x3

π = x4

x5

x6

x7

2π

g4 (x)

f (xj ) ! xj " # yj− yj+ $ $% N ! &'( )* a∗k b∗k +, -.

! f (x) " #$%& ! N = 8' h = π/4' xj = πj/4' j = 1, 2, . . . 8' ( . . a∗0 = π, a∗1 = −1.34076, a∗2 = 0, a∗3 = −0.230038, a∗4 = 0, b∗1 = b∗2 = b∗3 = 0. g4∗ (x) . g4∗ (x) = 1.57080 − 1.34076 cos(x) − 0.230038 cos(3x) ) * % + , !

/ & !!0 |a∗k − ak | |b∗k − bk | 1 2 $ $ 3 4

f (x) 2π N = 2n n ∈ N∗ f (xj ) xj ! " #$ %&'( ) * + a∗k b∗k , a∗k b∗k

= ak + aN −k + aN +k + a2N −k + a2N +k + . . . , (0 ≤ k ≤ n), = bk − bN −k + bN +k − b2N −k + b2N +k + . . . , (1 ≤ k ≤ n − 1),

|a∗k − ak | ≤

∞

{|aμN −k | + |aμN +k |},

μ=1

(0 ≤ k ≤ n),

5 667 5 687 5 6-7

|b∗k − bk | ≤

∞

{|bμN −k | + |bμN +k |},

(1 ≤ k ≤ n − 1).

μ=1

N ! " #! $ ak bk % ! f (x) !& ' ( N ) &! ε > 0 |a∗k − ak | ≤ ε |b∗k − bk | ≤ ε % k = 0, 1, 2, . . . , m < n

f (x) !" # $ % & ( 4 − 2 , $ k &

' a0 = π; ak = ( πk 0, $ k > 0 &

) N = 8 *& #$ & +$ $$ a∗0 = a0 + 2(a8 + a16 + a24 + a32 + . . .) = a0 , a∗1 = a1 + a7 + a9 + a15 + a17 + . . . = a1 −

4 π

j

ﬀ 1 1 1 1 + + + + ... . 49 81 225 289

,$ $ - * N +&$." ' $ $$ $ * *$ /" ak $ a∗k ' +$ * ε = 10−6

k &

k N & j ﬀ 1 4 1 1 1 a∗k − ak = − + + + + . . . π (N − k)2 (N + k)2 (2N − k)2 (2N + k)2 j ﬀ 2 2 2 2 8N + 2k 4 2N + 2k + + ... = − π (N 2 − k2 )2 (4N 2 − k2 )2 j ﬀ 1 1 1 8 + + + . . . ≈ − π N2 (2N )2 (3N )2 j ﬀ 4π 1 1 1 8 π2 8 =− + + + . . . =− · . = − 2 2 2 2 2 πN 1 2 3 πN 6 3N 2 0 1

& " 2 &+ $ $ 3 4 x = 0 $ # & & |a∗k − ak | ≤ ε = 10−6 & N > 2046

( ! *+ , ! "#! $ ak bk (2π)"- ! ! f (x) & . *+ / &! !0 , - 12 3 ! ,& . " 4, 5 1 *6 N ! !0 ! . ) 7 " 7 , . ! % , N = 2n #! $ a∗k k = 0, 1, . . . , n b∗k k = 1, 2, . . . , n − 1 N 2 8-! N 2 !! ! % )0 ( &! N N 1000 7 -!& !0 ( 9!

! "# $ " "% & '# # (' # )" "# # " *#% + % ,- , . ## + - + + /0 12 / , !

3 4 % ak := bk :=

N −1 j=0 N −1

N , 2

f (xj ) cos(kxj ),

k = 0, 1, 2, . . . ,

f (xj ) sin(kxj ),

N − 1, k = 1, 2, . . . , 2

j=0

5- /6

2π j

N xj = N

! " # $ $ %&"'() j * ! N − 1" + !

n = N/2 , yj := f (x2j ) + if (x2j+1 ),

j = 0, 1, . . . , n − 1,

n=

N . 2

%&"'(&)

, - yj .

/ n ck :=

n−1

yj e−ijk

j=0

wn := e

−i 2π n

2π n

n−1

yj wnjk , k = 0, 1, . . . , n − 1 j=0 # $ # $ 2π 2π − i sin . = cos n n =

%&"'(0)

- 123 wn

n 4 " - ,

ck

123 ak bk

ak bk ck 1 1 ak − ibk = (ck + c¯n−k ) + (ck − c¯n−k )e−ikπ/n %&"'(5) 2 2i 1 1 ck + cn−k ) + (¯ ck − cn−k )eikπ/n an−k − ibn−k = (¯ %&"'(6) 2 2i k = 0, 1, . . . , n, b0 = bn = 0 cn = c0

n−1 n−1 1 1 1 j(n−k) {yj wnjk + y¯j wn }= (yj + y¯j )wnjk , (ck + c¯n−k ) = 2 2 j=0 2 j=0

n−1 n−1 1 1 1 j(n−k) (ck − c¯n−k ) = {yj wnjk − y¯j wn }= (yj − y¯j )wnjk . 2i 2i j=0 2i j=0

!" # $%

=

1 1 (ck + c¯n−k ) + (ck − c¯n−k )e−ikπ/n 2 2i n−1 3 2 f (x2j )e−ijk2π/n + f (x2j+1 )e−ik(2j+1)π/n j=0

=

n−1

& f (x2j )[cos(kx2j ) − i sin(kx2j )]

j=0

+ f (x2j+1 )[cos(kx2j+1 ) − i sin(kx2j+1 )] = ak − ibk .

! " $% # k n−k

% & ' $ ( ak bk ) * + k ,

% - $ ' $

!. (/ ak an−k # % bk bn−k $ ( 0 - / / 1 ,$ ! $ 2 23 4 ! wn n2 5 # $ 6 wnjk 5 /+ 5% % 5/ $78$ n25 ! 5+/

% n 2 9 % $ % n = 4 ! 23 4 :+ W4 ∈ C4,4 3 ⎛ ⎞ ⎛ ⎞⎛ ⎞ c0 1 1 1 1 y0 ⎜ c1 ⎟ ⎜ 1 w 1 w 2 w 3 ⎟ ⎜ y 1 ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ , w = w4 ; c = W4 y ; ⎝ c2 ⎠ = ⎝ 1 w 2 1 w 2 ⎠ ⎝ y2 ⎠ c3

1

w3

w2

w1

y3

; / c & W4 # 7

/ :+ .

⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎛ ⎞ 1 1 1 1 c0 c˜0 y0 ⎜ c˜1 ⎟ ⎜ c2 ⎟ ⎜ 1 w2 1 ⎜ ⎟ w2 ⎟ ⎜ ⎟=⎜ ⎟=⎜ ⎟ ⎜ y1 ⎟ = 2 3 ⎠⎝ y ⎠ ⎝ c˜2 ⎠ ⎝ c1 ⎠ ⎝ 1 w w w 2 c˜3 1 ⎜ 1 ⎜ ⎝ 0 0 ⎛

1 w2 0 0

0 0 1 1

c3 0 0 1 w2

1

⎞⎛

1 ⎟⎜ 0 ⎟⎜ ⎠⎝ 1 0

w3 0 1 0 w1

w2 1 0 w2 0

w1 ⎞⎛

y3 ⎞ 0 y0 ⎜ ⎟ 1 ⎟ ⎟ ⎜ y1 ⎟ . ⎠ ⎝ y2 ⎠ 0 3 y3 w

! ""# $ % " # & '" " # $ " ! " ( % " )# * !

) + " ),

-) -

. / 0 y ! *" 0 z 1 / z 0 = y0 + y2 ,

2

z1 = y1 + y3 ,

z2 = (y0 − y2 )w0 ,

23

z3 = (y1 − y3 )w1 ,

, "# w = −1 w = −w " 4 5 ) 0' " " 23 / w0 = 1 )"), 4 -

5) z ! / . 2

3

1

c˜0 = c0 = z0 + z1 ,

c˜1 = c2 = z0 + w2 z1 ,

2

c˜2 = c1 = z2 + z3 ,

c˜3 = c3 = z2 + w2 z3 .

26

7 2 26 " 4 5 ) 0" ' " / w2 = −1 "), . w42 = w21 , ' "# # 2 26 ( /! '-)

% " '-) % "

2 23 ) '-) % " , "), 8 /! '-) " % " ) '-) ( % " 9"

' " " / -) ! "" :

" 5) " $ ) " * n = 2m, m ∈ N∗ " ), /! -) ck ; " 4 k = 2l# l = 0, 1, . . . , m − 1# c2l =

2m−1

yj wn2lj =

j=0

4 7

m−1

m−1

j=0

j=0

(yj + ym+j )wn2lj =

2l(m+j) wn

zj := yj + ym+j ,

(yj + ym+j )(wn2 )lj .

= wn2lj wn2lm = wn2lj m 5)

j = 0, 1, . . . , m − 1,

2

wn2 = wm m c2l =

m−1

jl zj wm ,

l = 0, 1, . . . , m − 1,

j=0

m !" zj # ck $ k = 2l + 1% l = 0, 1, . . . , m − 1% " c2l+1

=

2m−1

yj wn(2l+1)j

j=0

=

=

m−1

{yj wn(2l+1)j + ym+j wn(2l+1)(m+j) }

j=0

m−1

{yj −

ym+j }wn(2l+1)j

j=0

=

m−1

{(yj − ym+j )wnj }wn2lj .

j=0

& m !" zm+j := (yj − ym+j )wnj ,

j = 0, 1, . . . , m − 1,

m c2l+1 =

m−1

jl zm+j wm ,

'

l = 0, 1, . . . , m − 1,

j=0

m !" zm+j ( )#*+#, + -". n = 2m + -". m " "*, /*, m + -". &"-"+ $ n = 2γ , γ ∈ N∗ %

+0 1 m "1 2 ,"1 #*+ #, %

3 *, /+ 0 "*, $ "" n = 32 = 25 1 4 , " 5 *,1 16

2·8

4·4

8·2

16·1

F T32 → 2(F T16 ) → 4(F T8 ) → 8(F T4 ) → 16(F T2 ) → 32(F T1 ),

6

"*, F Tk k 1% )," "*, + -". &"-"+ # 17 /+

*, 1 ( 8 9 #1 % "" *, " /+

*, ," )," *, ck 8 + -". n = 2γ % γ ∈ N∗ 4 "" : 6 γ /+

*, n 8 #*+#,1 ( 2 ;*, n/2 + -". &"-"+ % 1 " /*, ZF T n =

1 1 nγ = n log2 n 2 2

n ! "!!#$ % &' () % * &+ (,) -. ! # / 0 $ 1 2 * n 3 n2 1 4 % 0 56$ 1 3 ZF T n 0 5$ 2 γ= n= n2 = ZF T n =

5 32 1024 80

6 64 4096 192

8 256 65536 1024

9 512 2.62 · 105 2304

10 1024 1.05 · 106 5120

11 2048 4.19 · 106 11264

12 4096 1.68 · 107 24576

Faktor

12.8

21.3

64

114

205

372

683

0 $

! # 2 n2 !

/ * 0 $ * - 7 ! # 1 * 4 1 * # y 8 c8

# 00 2 ! n = 16 = 24 !2 % w := e−i2π/16 = e−iπ/8 = cos(π/8) − i sin(π/8) 97: zj 0 0$ zm+j 0 $ yj ym+j 1 8 * 1 +7: 8 * ; %

* w 3 + * y 8 ! # ck * w / ! # ck > @ + N.

k=n

n > N |x| ≤ 1

|Tk (x)| ≤ 1 ∞ ∞ |f (x) − gn (x)| = ck Tk (x) ≤ |ck | < ε. k=n+1

k=n+1

!

f (x) = e

[−1, 1] gn (x) ! " # " $% & ' Zπ 2 ck = ecos ϕ cos(kϕ)dϕ = 2Ik (1), k = 0, 1, 2, . . . , & π x

0

" Ik (x) (% k) * ) +,' -&. ,/ 0 % /1 Ik (x) " . . . c2 = 0.2714953395, c0 = 2.5321317555, c1 = 1.1303182080, . . . c3 = 0.0443368498, c4 = 0.0054742404, c5 = 0.0005429263, & . . . c8 = 0.0000001992, c6 = 0.0000449773, c7 = 0.0000031984, . . c9 = 0.0000000110, c10 = 0.0000000006. 2 $% ck '

3 / 4 % 5 6 7) 8 % ! f (x) ' ' / 9 % '4 : % ;% < /1 1 g6 (x) " & 0

!"#$ (n + 1) ( k = j = 0 !"#$ ) *

!""'$ !""'$ + , -

. !""/$

0 1 0 2 1 γ0 , γ1 , . . . , γn

- ,0 34 !""/$ 0 l5 - !""/$ Tj (xl ) j ( , 0 ≤ j ≤ n (n + 1) - 6 1 !""'$ ( , 7 8 γk

γk

= =

n+1 2 f (xl )Tk (xl ) n+1 l=1 $$ # $ # n+1 # 2l − 1 π 2l − 1 π 2 cos k , f cos n+1 n+1 2 n+1 2

!" $

l=1

k = 0, 1, . . . , n.

)1 1 8 γk 0 9. Pn∗ (x) : 5 . ;5*

Tn+1 (x)

7 8 c∗k !"" $ * 7 8 1 9. n5 - 1 ∗ 1 c0 T0 (x) + c∗k Tk (x) + c∗n Tn (x) 2 2 n−1

gn∗ (x) :=

!""$

k=1

N # 0 ) 5 2 # $ jπ (e)

(n + 1) ), xj = cos Tn (x) ( n ( 01 ±1 ( 0 0. gn∗ (x) gn∗ (x) * !"" 2m* - 0 "

* Im,n = 0 - . 1# $%&%2' $%&%' "

* - ! m = n ! 3 d2n [(x2 − 1)n ] = (2n)! dx2n

) $%&%' n # "

)1 In,n

(x − 1)n (x + 1)n dx

n

= (−1) (2n)! −1

1 1 n+1 = (−1) (2n)! (x − 1) (x + 1) n+1 −1 ⎤ 1 ) n − (x − 1)n−1 (x + 1)n+1 dx⎦ = · · · n+1 n

n

−1

n(n − 1)(n − 2) . . . 1 = (−1) (2n!) (n + 1)(n + 2)(n + 3) . . . (2n)

)1

2n

(x + 1)2n dx −1

22n+1 . = (n!)2 · 2n + 1

!"# $% Pn (x) &$ x '() !* n ($ ($ +## &$ x , &$ #$)% ) n , -() Pn (−x) = (−1)n Pn (x),

.

n ∈ N. Pn (x) n ≥ 1

(−1, 1) n

) /()% (x2 − 1)n 0 x = ±1 1 n () 2 ,% () n # 3 4 , dk ,()% [(x2 − 1)n ] 0 x = ±1 k = 1, 2, . . . , n − 1 1 (n − k) () dxk 2 -5 # n ' () 2 # 6 [−1, 1] !"# n 7 n 2 80($() ) 9()) ,% 8)'

2 Pn (x) $: 0 # n () # & / !"# () () &# , 6) # ,' ;, % 3() % 3 < ,

! "# P0 (x)

=

1,

P1 (x) = x,

Pn+1 (x)

=

2n + 1 n x Pn (x) − Pn−1 (x), n+1 n+1

= n = 1, 2, . . . .

- $ # % 1# () L2 3$'$ 3"# ) !"# , 3"# 0 /# 4$ 3"# >, ,##% ) ; ?,
> e− . n

+ − In /n, < e « j„ ﬀ & '(9) In−1 = > 1 > : − In /n, e+ . n

+ e

.1 3 N IN = 0 * 1 " " + 1 N = 24 " 7 : % 9 4

I0 % I6 " ;!" c0 % c6 : % 9 !" k

Ik

ck

< @ '

' 00===' ( ===(9''9