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 / <) ) = 17 * ; !
6 +) + + " " ) > 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 : & ;<) - %& # 3 + <)
= &
"9 1%& %& (
1%& %& (
' #
! ! , ,
*0
,
"0
1& %& . # + ) & # - %&%& 39 2 ) * 4 # + #
! " $%$&
" (%) * +
,- " / 0 $& - *")% 0
. .
#
!
#
'
1
#
# '
2 ,- " 3 " !-"" 4 )" 4" / "+
#
5 $
# # #
&
# # # #
2 " " 2 " 6 $(" 2 " (" ! $2 "
.
## ## ## ## ## ###
QR$1 " + QR$2 " , 7 8 4 QR$)) 8 ")% 4 QR$1 " 7 &+ : 4
9 # #' '
#' #'
" 4 )" -"" ) ; (
' '
#.
4 8 * 8 !<
'
#9
1 0 &"
'9
#
!
.
#
1
.
# # # # #
*
!" #$ &' () + #$
%
*
& , - '
%
! .#-# "
% % *
/
&-
*
*/
-#0 #1 2 ) " -#0 #1 3 $ '
* * *
( #4
* *
* * * **
$ 5 4 4 6 R 3
* / * * *
! .#4 7 ! .#(
** **
/
" 4
**
4 5 ) 4 6 &
** ** **
&-
**
**%
!
76 5 )
! 8) 8
** ** */
*
7 " 2 ' ( #2 #3 79' ( #2 #3
*/ */ */* */
! " "$ %&'( $" $ & )$) $
# # #
* ,* , * % $ * - " % $ * ! " / 0
+# +# + .
%&1 2$)$ 3 $&
#
$
+
%
4$ & 5
2 & % 26 %( !$& %( !$& 7) $*
. .
8" / - 8" / ! 8"
. .
/ 0 " / " & / 0 / ) & &
$
#
%
. . . . . .
. . . .
/ 0 " 4$ / ) & % & 9 ): & & / ) -*
+ + #
4 $ %& - & $ 4$ : ;
!$& - & $ 4$ :
!$& / 0 $ " $<
&
! #$ ! % !
" "" ""
'$
(
&
#$
(
) * ) + %
("
,- .$ / * 0 .$ / . 1 2 ,- / . % *
( ( &&
& " (
%$ 1$ 3% 40 0 $5 .$ ) 42 $5 6 1 7* /- 1 8% 9
* : 8 # %$ * : / . %1 6*
&( &( & & & & " & & &
&" &" & && &
& & &
. , 6$ # % ! % %$
&& && &(
' % %%
&&
"
'$
&&
(
#$
&&
! " #
! ' (( ) # "
" $ %&
* ) + # " , -
)' ./ 0 #
" " 0" + & $
1" # 2 -
! "!
! !
0" * 3 * # " 0 & & " & 4 + 0 ! $ */
5 ) $ */ &
!6
6 0 */ &+ 5
# - * 0 ' *+
! 7 8 " 1
+ 7 !
6 5$ #
!
" & % + 3 % / & ) 1 " & ! !9 &+& * 2& $
! 5 %
! ! " # $ % & '%( ) * ( + , ( %% # ( ( * - ! . )/ % # % ) 0( ( #
# 3# 4# # 8# :# =# >#
).( ) ).( & & & 6 , ) !
1 1 1 1 1 1 1 1
2%( $5 #2# 7 & ' ! 79 7 ;< $ ( ( $
$ ! & ?# @ ! ,( 9 ) # $ % , # $ ) A + 2 ( ) 9 # ( # )( 9 " 2 # ' &( ) 9 B9 *9B 2 &9'
9 % *B2 # $% ) * % ( 8#C # @-(9 6 ( A % #
% & ( + * %# 7 ( DE :> ? C ? >3 ? =3 F >3 F8G ! , D$ >: ' C8 ' C: " CFG ( H 9! , 9 & (% D7& CF ' C3 ? >> ( 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 .
< 2 ½
M
x = 0 rd(x)
|rd(x) − x|
≤
|rd(x) − x| |x|
≤
E e−k 2 1 1−k E =τ 2
x > 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 ˙ <
|δy | ≈ 5τ.
x
0
y
! x
(1)
(0)
=
x,
=ϕ
=
x(2) = ϕ(1) (x(1) ) =
2x 1+x
(x) = (1)
x1
(1)
x2
: R → R2 ,
: R2 → R.
0 1 0 1 ! (1) 1 1 x −2x 2 1 A=@ A, Dϕ(0) = , Dϕ(1) = @ (1) , − (1) , 1 + x (1 + x)2 1 x2 (x2 )2 Dψ (1)
=
Dϕ(1) ,
Dϕ
=
2 . (1 + x)2
δy
. =
0 1 (1) −x 1 2δx 1 + @ (1) , (1) A (1 + x)2 x2 (x2 )2
=
2δx (1) 2x (1) (−2x) (2) 2x + ε1 + ε2 + ε1 (1 + x)2 1+x 1+x 1+x
(1)
ε1 0
!
! 0 (1)
ε2
2x 1+x
(2)
+ ε1
2x 1+x
˙ <
|δy | ≈ 2τ.
x = 1 · 10−3 ! y" = 1.998001998 · 10−3 E = 10, k = 8 :
# y = 1.9980000 · 10−3 ,
# y = 1.9980020 · 10−3 .
! $ % & $ ' '( ! ) * ! !
y = ϕ(x) !" # # y˜ = ϕ(˜ ˜ x)
δx y˜ = ϕ(x + δx )
y˜ x + δx ϕ y˜ ! " # $ ||δx ||! %
# δx &'( # ) ||δx || ≈ ||x|| τ
! * + , + -. /01 -. 21!
3 4 + 5 & ! * 3 * & 6% 78 " ,9 ( & ) & 6: 8 , 3 #! + # ; # , # 6 -; <=18
> 3 4' 33 4'
& 9 " 3 33!?
0/0 0/0 ! " # $% & " " % " ! ' (
x1 · x2 x1 · x2 x3 · x4 . x3 · x4 ) * " & . εy = (εx1 + εx2 ) − (εx3 + εx4 ). y=
+ , '.( x1 − x2 x1 ≈ x2 , x3 ≈ x4 . x3 − x4 / " * „ « „ « x2 x4 x1 x3 . εy = εx − εx − εx − εx . x1 − x2 1 x1 − x2 2 x3 − x4 3 x3 − x4 4 y=
0 x1 ≈ x2 x3 ≈ x4 & 1 2 3 ' ( " 4 , 4
"
S=
n X
ai
i=0
S0
:=
a0 ,
Si
:=
Si−1 + ai i = 1, . . . , n,
S
:=
Sn .
δSi = δSi−1 + δai + τi |τi | ≤ τ |Si | =⇒
δS = δSn =
n X
δai +
i=0
n X
τi .
i=1
|δai | ≤ τ |ai | „X « n n X |δS | ≤ τ |ai | + |Si | . i=0
i=1
n X
τ |εS | ≤ |S|
|ai | +
i=0
n X
!
|Si | .
i=1
! "! ! # $ %& # # ' &(& a0 > a1 > a2 · · · > 0, # S0
:=
an ,
Si
:=
Si−1 + an−i i = 1, . . . , n,
S
:=
Sn .
( ) # # * e−x ≈
N X
(−1)i
i=0
xi . i!
x 0 N ! " # & ) "! " x ≈ i " i% "# xi & k + , $! - xk+1 x xk ≥ ⇒ ≤ 1 ⇒ x ≈ k. k! (k + 1)! k+1
- .$! ex xx ≈ √ x! 2πx
/ .
«ffi „ τ e2x ex √ e−x = √ τ 2πx 2πx
x 0 ! " # x e−x $ ex %
≤ 1 : ffi xk ex < τ τ k! & % 1/ex e−x #
'( " x = 10% τ = 5 · 10−10 & e2x . √ = 6.1 · 107 2πx & # )* ' + # , -% '
. / e−10 = 4.5399930 · 10−5
& 0 1 e−x 2 34 & )* & 1 ex 2 ), 5 $
/ 1# & 6 1 # 2 0
7% # 2 # , + $ 1 e−x ex k X
(−1)i
k
exp(−x) ≈
8
8 9:8 3 8 9 ,;4 ,: 8 )3,;<4 ;3;8883 8888:4 4;;: 8888 );: 888883< ; 888883< 3,;,
, ) 3 8 ,8 )8 ), 38 34
i=0
xi i!
exp(x) ≈
k X xi i! i=0
8 8 8 ,,44 33)))) ,<3,) , :: 3< ,,8,33 ,,8,3
π ! τ "# $% & ' () *
& +) , . ) / . τ ≈ 10−8 / )) . τ ≈ 10−16
0 /' ! ! τ = 1 )/ . )
x y x, y ∈ M 2 E −1 τ 2 τ |x| τ !
" # $ 1−x 2x f (x) = 1 − g(x) = 1+x 1+x % & $ & x = 1/7654321 & ' & ! ( & ) * # ! $ & * + & !
f (x) := ex , x ∈ Ê f
d1 (h) =
1 1+h − e) (e h
d2 (h) =
1 1+h − e1−h ) (e 2h
f (1) (0 = h ∈ Ê) d1 (h) d2 (h) |d1 (h) − f (1)| |d2 (h) − f (1)| h := 10−i ,
d1 (h) d2 (h)
i = 0, 1, 2, . . . , 18,
!" # $% & f d1 d2 '
( $ )*+ { x ∈ [0, 2π] | x , } - )*+ & , + .. / ' 0 & #. cos(0.614) = 0.8173499969 . . . ,
1 t (cos(0.614)) t = 4, . . . , 9
4 (t (cos(0.614)))
π ≈ 3.141592653589793238462643383305
π = lim 3 · 2n−1 sn = lim 3 · 2n−1 tn n−→∞
n−→∞
q
()
s1 := 1
sn+1 :=
2−
p
()
t1 := 1
tn+1 := p
2+
4 − s2n
tn √
4 − t2n
n = 1, 2, . . . , n = 1, 2, . . .
() !
" #$ %! & sn '
( 3 · 2n ) * +
* , sn = tn n ∈ N * * q - p ϕ(x) := 2 − 4 − x2 . . # * " ϕ(x) +
. x = 0/ * #+ .
3 · 2n−1 sn
3 · 2n−1 tn
n = 1, . . . , 35 * 0 * * 1 *
Ê
p
#$ * ξ0 ∈ + g
23$ p+
∈ *
2 #$
Ê
p := p + g.
, +
%4 "5 U " 6 - ξ : U −→ • ξ(0) = ξ0 + • ξ( ) " p ∈ U +
Ê
p(ξ( )) + g(ξ( )) = 0
∈ U
• ξ( ) * " p ∈ U , +
ξ(·) U - .
ξ( ) = ξ0 −
g(ξ0 )
p (ξ0 )
!" ! #$ ! % &! ' (! ) ! !" * ' + ! , & ' !" & # -./ )" 0 % !' #$ 1 ' $ ! ! 2 -./ # "% 3 ' -./ 4 ' & ! 5 " %
1' - 6 0 3 7 ' -!% $/ #8 2 ) ' - 99
0 n
k=1
aik xk = bi ,
i = 1, 2, . . . , n,
:;9<
n n = xk -. aik - bi , > = xk
:;9< # ! Ax = b :;;< 4 (n × n)% / A' 3 b x =% )" ) ' -./ A # ' 0/ 0 x :;;< ?@ AB' 3 ACD
!"# $ % & ' n = 4 & ( '& " x1
x2
x3
x4
1
a11 a21 a31 a41
a12 a22 a32 a42
a13 a23 a33 a43
a14 a24 a34 a44
b1 b2 b3 b4
!" #
) !" # *&+ aik ,- A *&& bi b" . !" # & /01 && % 2 !"# ) && 1( 3 " 1& 4 !" ,& = 04 " .& " 5 . a11 = 0 1& i$ i ≥ 2 (ai1 /a11 )$
!" # x1
x2
x3
x4
1
a11
a12
a13
a14
b1
0
a22
0
a32
0
a42
(1)
a23
(1)
a24
(1)
a33
(1)
a43
(1)
b2
(1)
a34
(1)
a44
(1)
(1)
b3
(1)
b4
!"6#
(1) (1)
, 7& li1 = ai1 /a11 ,
i = 2, 3, . . . , n,
!"8#
9 !"6# (1)
aik = aik − li1 a1k , (1)
bi
= bi − li1 b1 ,
i, k = 2, 3, . . . , n,
i = 2, 3, . . . , n.
!":# !";#
!"6# !"# (01 2" $ ( 5 x1 % & 5 ( (< n x1 = b1 − a1k xk /a11 . !"=# k=2
> ( !"6# ' 2 1& (n − 1)
(n − 1) 5 x2 , x3 , . . . , xn " ? 1& !" # !"6#
n (n − 1) !"# #" $" " "!" " " % & '"( " ) ! " * a11 " " * " "+ " (1)
" " " a22 = 0 " & , ! * " x1
x2
x3
x4
1
a11
a12
a13
a14
b1
0
a22
a23
0
0
a33
0
0
a43
(1)
(1)
a24
(1)
b2
(2)
a34
(2)
a44
(1)
(2)
b3
(2)
b4
-
(2) (2)
) . "+ (1)
(1)
li2 = ai2 /a22 ,
/
i = 3, 4, . . . , n,
* - (2)
(1)
(1)
(1)
− li2 b2 ,
aik = aik − li2 a2k , (2)
bi
= bi
(1)
i, k = 3, 4, . . . , n, i = 3, 4, . . . , n.
0 - ( ! * #" x2 n (1) (1) (1) x2 = b2 − a2k xk /a22 .
k=3
0 1 2"! " * " #" (n − 1) " ! " * ( 34! " * ! ! 5 " " (0)
aik := aik ,
i, k = 1, 2, . . . , n;
(0)
bi
:= bi , i = 1, 2, . . . , n, ⎫ (i−1) rik := aik , k = i, i + 1, . . . , n, ⎬ i = 1, 2, . . . , n. (i−1) ⎭ ci := bi ,
& 6
0 " * x1
x2
x3
x4
1
r11 0 0 0
r12 r22 0 0
r13 r23 r33 0
r14 r24 r34 r44
c1 c2 c3 c4
7
xn xn−1 . . . x2 x1 n xi = ci − rik xk /rii , i = n, n − 1, . . . , 2, 1, !
k=i+1
" ! #$ % % & & " & % ' ( % ' ) Ax = b *) Rx = c & R ⎛ ⎜ ⎜ ⎜ R=⎜ ⎜ ⎝
r11 0 0
r12 r22 0
r13 r23 r33
0
0
0
··· ··· ···
r1n r2n r3n
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
+
· · · rnn
, (
2x1 4x1 −6x1
+ + +
3x2 8x2 x2
− − +
5x3 3x3 4x3
= = =
−10 −19 −11
x1 2 4 −6
x2 3 8 1
x3 −5 −3 4
1 −10 −19 −11
x1 2 0 0
x2 3 2 10
x3 −5 7 −11
1 −10 1 −41
x1 2 0 0
x2 3 2 0
x3 −5 7 −46
1 −10 1 −46
! " " #"! $ % &' x3 = 1( x2 = (1 − 7 · 1)/2 = −3 x1 = (−10 − 3 · (−3) + 5)/2 = 2
- ,. ' & / & $ * 0 1 * *) % . % 0 , 2 $. ' $ 3 * 4 5 lik $ 1 &
x1
x2
x3
x4
1
r11
r12
r13
r14
c1
l21
r22
r23
r24
c2
l31
l32
r33
r34
c3
l41
l42
l43
r44
c4
! "#$ % &' & ( ) &*+ , - rik i$ % i ≥ 2 k ≥ i (i − 1) ( $ . ' / (i−1)
rik = aik
(0)
(1)
(i−2)
aik − li1 a1k − li2 a2k − . . . − li,i−1 ai−1,k aik − li1 r1k − li2 r2k − . . . − li,i−1 ri−1,k , i ≥ 2, k ≥ i.
= =
, 0) aik =
i−1
lij rjk + rik ,
1
(k ≥ i ≥ 1),
j=1
* i = 1 *+ &.' , - lik k $ (k−1) 2 k ≥ 2 i > k k $ ( aik . lik
= =
(k−1)
(k−1)
(0)
(1)
(k−2)
(k−1)
aik /akk = [aik − li1 a1k − li2 a2k − . . . − li,k−1 ak−1,k ]/akk [aik − li1 r1k − li2 r2k − . . . − li,k−1 rk−1,k ]/rkk .
3 aik ' 0) aik =
k
lij rjk ,
(i > k ≥ 1),
j=1
/ * k = 1 * , & 4 1 4 5)2+ & 4+6 R 7 8 L ( , ⎞ ⎛ 1 0 0 ... 0 ⎜ l21 1 0 ... 0 ⎟ ⎟ ⎜ ⎜ l31 l32 1 ... 0 ⎟ L=⎜ ⎟. ⎜
⎟ ⎠ ⎝
ln1
ln2
ln3
... 1
, 1 . & 5) A = LR.
(1)
(2)
(n−1) a11 = 0, a22 = 0, a33 = 0, . . . , ann = 0
!" A #" L $" R ci i ≥ 2 (i−1)
ci = b i
(1)
(i−2)
= bi − li1 b1 − li2 b2 − . . . − li,i−1 bi−1 = bi − li1 c1 − li2 c2 − . . . − li,i−1 ci−1 , (i ≥ 2).
bi =
i−1
lij cj + ci ,
i = 1, 2, . . . , n,
j=1
! "
" # L $% % $ &
Lc = b.
' "% c ( & " % !) * + & ,
L ! "
" # -
.- " ci / $% c1 c2 , . . . , cn 0 ) 1 % %& ' 23 ci = b i −
i−1
lij cj ,
i = 1, 2, . . . , n.
j=1
4$ * " !) x
* + Ax = b '% ( 0 *3 4%
!) -
5 1. A = LR ( 6 0% A) 2. Lc = b ( '% 2 - % → c) 3. Rx = c ( / "- % → x)
7
% '%
6 0 $ 0% 8 9 % $
$ " % ' $
%
$ -
!" A " k( ( )* k(
+& 0% / 2 : # A -
|A| = 0 *34% $ ;% < : # A 6 %, % - ' -
=, % $ ) 4 % a11 = 0 # ai1 = 0 (, $ 2
0% A , '%
i (1, 1) v1 = 1! " # ! v1 = 0! " a11 = 0 $ " " % & ' ( aik ! ) "* n = 4+
|A| =
(−1)v1
a11 a21 a31 a41
a12 a22 a32 a42 (1)
=
(−1)v1 a11
a22 (1) a32 (1) a42
a13 a23 a33 a43 (1)
a23 (1) a33 (1) a43
a14 a24 = (−1)v1 a34 a44
a11 0 0 0
a12 (1) a22 (1) a32 (1) a42
a13 (1) a23 (1) a33 (1) a43
a14 (1) a24 (1) a34 (1) a44
(1)
a24 (1) a34 (1) a44
),,-+
),+ . /#0 1 "* * %0 " " ! 2 ! # ( (1) aj2 = 0! " ),,-+ |A| * j ),!,+
rkk ! k = 1, 2, . . . , n − 1! k ! ! rnn "* n ! 3 "* "* ,,
|A| |A| = (−1)
V
n
V =
n−1
vi
i=1
), 4+
rkk .
k=1
|A| 2 ( A ! ! & n / 0$ & 5 6& $7# / 2 & ! & $ & ),, + |L| = 1 " ! n |A| = |LR| = |L| |R| = rkk . k=1
!" # $ %&$ '( " )* + # + ", Ax = b " * $$ - $ . &$& ", ", /0 A * " ! " 1 $ 1 * 2 " " 1 ", * # 3 ", * 2 4 + ", $ 1 5 " P $ 6 /0* 2 1 2 .5 4 7 * |P | = ±1 $ " # 8 . &$9 &$&
A P P A L R !" # %&$ 9(
P A = LR.
. &$: %&$&;( , $ Ax = b +0 P 5 < P Ax = P b* = x " < 1. P A = LR 2. Lc = P b 3. Rx = c
%1 P A) %! → c) %3, → x)
%&$ &(
1 5 /0 A + ! " . b $ 3" . n n > $ / 5 * " ?5
$ - j 4 # 1 P A = LR (j)
%&$@( %&$A( (n − j) B lij (n − j)2 C aik $ D [(n − j) + (n − j)2 ] ?5 " * 3" ", 1 ZLR
= {(n − 1) + (n − 2) + . . . + 1} + {(n − 1)2 + (n − 2)2 + . . . + 12 } =
1 1 1 n(n − 1) + n(n − 1)(2n − 1) = (n3 − n) 2 6 3
%&$
(
ci ! (i − 1) "#$#% & # ' ( ) 1 1 ZV = {1 + 2 + . . . + (n − 1)} = n(n − 1) = (n2 − n) *! 2 2 +#,# xi - ! (n − i) "#$#% . & # ' ( '(% 1 1 ZR = {1 + 2 + . . . + n} = n(n + 1) = (n2 + n) /! 2 2 + # ' ( & '# ) '(% 0!
Z V R = n2
# 1$ . ## ,)2# 3 n # # Z
1
1
= 3 n3 + n2 − 3 n = O(n3 )
!
# ' $ O(n3 ) & 2 ') 4$ 5# 6% #
. + * # 78 ## # ( % 7# + # % % 9# : ;( .( ,)2# %, 2# ( % 3 5 < = '# #& #
9 # % . # #& $
+ % 5# . % ,)2# & # "8 A ) # & & + < ;## & # # #
! " " #$ % & ' " " ( )*) " &
)* " &+ ,$-$ % % . ) x1 x2 1 x2 1 −→ 1.2654 3.5267 0.00035 1.2654 3.5267 1.3182 6.8541 0 −4535.0 −12636 . l21 = 1.2547/0.00035 = 3584.9 " " " . . / r22 = 1.3182 − 3584.9 × 1.2654 = 1.3182 − 4536.3 = −4535.0 x1 0.00035 1.2547
. . c2 = 6.8541 − 3584.9 × (3.5267) = 6.8541 − 12643 = −12636 . . x2 = −12636/(−4535.0) = 2.7863 x1 = (3.5267 − 1.2654 × 2.7863)/0.00035 = . (3.5267 − 3.5258)/0.00035 = 0.0009/0.00035 = 2.5714 (1) (1) ! r22 = a22 c2 = b2 " # x2 $ % & # # x1 ' ( ! ) * # x1 + , %
. . - . x1 = 2.5354 x2 = 2.7863) x2
( %
- /* $ (+ x1 * 0 1 2 (
A ! " # $ % &! %' ( ) $ " n |aii | > |aik |, i = 1, 2, . . . , n. *+ ,k=1 k = i
! " n |aii | ≥ |aik |, i = 1, 2, . . . , n,
*+ -
k=1 k = i
( i0 *+ - . /
A
'. $ #" ( . / n |a11 | > |a1k | ≥ 0 0 a11 = 0 ' 1 (
k=2
2 " (' 3 *+4- *+5- ( (1)
aik = aik −
ai1 a1k , a11
*+67-
i, k = 2, 3, . . . , n.
0( 8' (1) |aii |
ai1 a1i ai1 a1i , ≥ |aii | − = aii − a11 a11
i = 2, 3, . . . , n.
*+69-
i i = 2, 3, . . . , n !"#$% &' !" (% ) * n
(1) |aik |
=
k=2 k = i
k=2 k = i
n
=
n aik − ai1 a1k ≤ a11
k=1 k = i
n k=2 k = i
n ai1 |aik | + |a1k | a11 k=2 k = i
n ai1 |aik | − |ai1 | + |a1k | − |a1i | a11 k=2
ai1 {|a11 | − |a1i |} = |aii | − ai1 a1i ≤ |a(1) |. ≤ |aii | − |ai1 | + ii a11 a11 (1)
+ |a22 | ≥
n
(1)
(1)
|a2k | ≥ 0 |a22 | > 0 ,
k=3
-
. / " & 0 (1) a22 1. 2" 1. . . ' & 3 0 , ' 2 1. " 4 - 3 . " & k , ' 5 6 p (k−1)
max |aik i≥k
(k−1)
| = |apk
!" !%
|.
3 p = k p k . " 4
(k−1) (k−1) 7 lik = aik /akk (i > k) ' 8 , '
0 " 3 30 0 k - 0 , 3 -9 . / 0 0"
! "#" $ x1 1.2547 0.00035
x2 1.3182 1.2654
1 6.8541 3.5267
−→
x1 1.2547 0
x2 1.3182 1.2650
1 6.8541 3.5248
% & l21 = 0.00027895 ' ( . ) % $# x2 = 2.7864 . . x1 = (6.8541 − 1.3182 × 2.7864)/1.2547 = (6.8541 − 3.6730)/1.2547 = 3.1811/1.2547 = 2.5353 % * + ( )
% ,
! " #
$ % & '
(
l) x1 2.1 −1.3 0.9
x2 2512 8.8 −6.2
x3 −2516 −7.6 4.6
1 6.5 −5.3 2.9
x1 2.1 −0.61905 0.42857
−→
x2 2512 1563.9 −1082.8
x3 −2516 −1565.1 1082.9
1 6.5 −1.2762 0.11430
x3 1 −2516 6.5 −→ −1565.1 −1.2762 −0.70000 −0.76930 . . . ! *+ ,% x3 = 1.0990 x2 = 1.0990 x1 = 5.1905 * ) x3 = x2 = 1 x1 = 5 ! * -
. ! /0 a(1) ik ! '+ $ & ! 1 + a(2) 33 * %
# .! 2+ . * 3 4 1 #! 4 & ( 5 678 . ai1 a1k " ) $ * -
$ x1 2.1 −0.61905 0.42857
x2 2512 1563.9 −0.69237
a ˜ik n |˜ aik | ≈ 1, i = 1, 2, . . . , n. !" #$ k=1
% & ' (& ( ) *) + , ' -. ,(/" - ) |˜ aik | ≤ 1 i, k = 1, 2, . . . , n ( / 0 + (& 1( ' ( 2/ !"3 "
+ 1 $ * x1 0.00041749 −0.073446 0.076923
x2 0.49939 0.49718 −0.52991
6 * ! #
x3 −0.50019 −0.42938 0.39316
1 0.0012922 −0.29944 0.24786
! a31 2+ ( & +
. x1 0.076923 −0.95480 0.0054274
x2 −0.52991 −0.0087800 0.50227
x3 0.39316 −0.053990 −0.50232
1 0.24786 −0.062780 −0.000053000
! x1 0.076923 0.0054274 −0.95480
x2 −0.52991 0.50227 −0.017481
x3 0.39316 −0.50232 −0.062771
1 0.24786 −0.000053000 −0.062781
. . . "# ! $ x3 = 1.0002, x2 = 1.0002 x1 = 5.0003 %& ' $# ( )! ! * !&
! "# $% &
' ( )!&* # + # ' , & ! & & & * * % * - * # . & /& # % * +, # !&
& % & # 0 " )!& ! * % *& # + * 1 . 2 & ' 3 )!&% * " ! " ' 4 ,
5 4 6 # !& 7&
k , ' & 8 + p &% ⎫ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (k−1) ⎬ ⎨ |a(k−1) | ⎪ |apk | ik = n . max n ⎪ k≤i≤n ⎪ ⎪ (k−1) ⎪ (k−1) ⎪ ⎪ ⎪ |aij |⎪ |apj | ⎭ ⎩ j=k
j=k
8 p = k % * p, 5 k , 5 ! " ! 9& lik (i > k) '
* + , ! $#$ " ( ) " ! $ ! n X (k−1) *& si = |aij | j=k
qi = |a(k−1) |/si ik a31 ! " # $ x1 2.1 −1.3 0.9
x2 2512 8.8 −6.2
x3 −2516 −7.6 4.6
1 6.5 −5.3 2.9
si 5030.1 17.7 11.7
qi 0.00041749 0.073446 0.076923
x1 0.9 −1.4444 2.3333
x2 −6.2 −0.15530 2526.5
x3 4.6 −0.95580 −2526.7
x1 0.9 2.3333 −1.4444
x2 −6.2 2526.5 −0.000061468
1 2.9 −1.1112 −0.26660
x3 4.6 −2526.7 −1.1111
si − 1.1111 5053.2
qi − 0.13977 0.49998
1 2.9 −0.26660 −1.1112
. . . x3 = 1.0001 x2 = 1.0001 x1 = 5.0001 . 2 A !"# |A| = (−1) × 0.9 × 2526.5 × (−1.1111) = −2526.5 $ |A| = −2526.504
! "
# $ % & ' (
#$%
"
& ' ) * + (k−1) , + & - . aij / (k)
- lij aij ) , . lij ) aij " 01"
2 +
' aij = lij $ i > j, aij = rij $ i ≤ j & 3 $ ' (% p = (p1 , p2 , . . . , pn )T & k 0 + 34 5 ' k
k '
% ( pk = k 3 2 6 7 ) " ) $ + 2 (
% 8 % c b 9" bi - ci & " (% b & , $ #$% :- % x c ; b<= 9" 6 )
) b :- % x
3 6
7 01" 4 A ) b " " - & :-
; = 6 ) & ' P A = LR > $ " " 3 $ '
b
det = 1 k = 1, 2, . . . , n − 1 : max = 0; pk = 0
k = 1, 2, . . . , n − 1 :
i = k, k + 1, . . . , n : s=0 j = k, k + 1, . . . , n : s = s + |aij | q = |aik |/s q > max : max = q; pk = i max = 0 : pk = k : det = − det j = 1, 2, . . . , n : h = akj ; akj = apk ,j ; apk ,j = h det = det ×akk i = k + 1, k + 2, . . . n : aik = aik /akk j = k + 1, k + 2, . . . , n : aij = aij − aik × akj det = det ×ann
pk = k : h = bk ; bk = bpk ; bpk = h
i = 1, 2, . . . , n : ci = b i
j = 1, 2, . . . , i − 1 : ci = ci − aij × cj
i = n, n − 1, . . . , 1 : s = ci
k = i + 1, i + 2, . . . , n : s = s − aik × xk xi = s/aii
!
! !
! m " # $ $ b1 % b2 , . . .% bm ! & % ! $' ! () *+ ,-
B = (b1 , b2 , . . . , bm ) ∈ Rn,m
!$$
() X ∈ R AX = B
n,m
.& (! *+ /-
0 X .& xμ ! 0 bμ
1 Z = (n3 − n) + mn2 . 3 ! "!## $ !% ! ! & # '!( A )! * X = A−1 +## ! '! #! ,
AX = I, −1
I ! )! - * A ! .! ! #!!! n /#! .! # '!( A +%+ ) & . #!"#!%! 0"! # ! 4 1 ZÁÒÚ = n3 − n. 1 3 3 )! ! ##! ! +%!!2 3!# ". ! ! I & # ! #. ## ) 4 5 ! ! # !. 4! !" !. 6!#! ! #. !
2 .! ! %! & "! )! '#!%! ! ! ".. % . )! - A−1 ! $ . 7"!"# + A 6 ! + I 2 7## %! ! * ! ) 7"! ##! 2n2 4#
. /#! 8. Ax = b .! .! . / 9&$#!. 2 # . / .!#! # ## (% % ˜ )! ! " ! /#! ! !. $##.! x ! x ## ##% ! r := A˜ x − b.
:
˜ ## ! (% x .! ;!# $ . %
% x
x=x ˜+z
<
.!# ) =% % z ! !.. 2 ! /#! +## ! 2 !# Ax − b = A(˜ x + z) − b = A˜ x + Az − b = 0.
- . ! ! /#! :2 %
. 2 =% % z /#! 8. Az = −r
.! # '!( A2 7! −r +## . )! =% z ! ! .! ! 4 5& +% ! ! . ! & % r2 .! ""# / !%! . 2 ! -!"!#
! "# 0.29412x1 0.42857x1 0.36842x1 0.38462x1
+ 0.41176x2 + 0.57143x2 + 0.52632x2 + 0.53846x2
+ 0.52941x3 + 0.71429x3 + 0.42105x3 + 0.46154x3
+ 0.58824x4 + 0.64286x4 + 0.36842x4 + 0.38462x4
= 0.17642 = 0.21431 = 0.15792 = 0.15380
$ % ! & A %# ' & ( ) ( % % si " & * qi x1
x2
x3
x4
0.29412 0.42857 0.36842 0.38462
0.41176 0.57143 0.52632 0.53846
0.52941 0.71429 0.42105 0.46154
0.58824 0.64286 0.36842 0.38462
si 1.8235 2.3572 1.6842 1.7692
x1
x2
x3
x4
0.36842
0.52632
0.42105
0.36842
1.1633 0.79833 1.0440
−0.040840 −0.0084200 −0.011020
0.22448 0.19327 0.021960
x1 0.36842 1.0440 0.79833 1.1633 x1 0.36842 1.0440 1.1633 0.79833
x2 0.52632 −0.011020 0.76407 3.7060 x2 0.52632 −0.011020 3.7060 0.76407
x3 0.42105 0.021960 0.17649 0.14310 x3 0.42105 0.021960 0.14310 1.2333
0.21428 0.29412 −0.00001 x4
0.36842 −0.00001 0.29413 0.21432
si − 0.47960 0.49581 0.032980 si − − 0.47062 0.35742
qi 0.16129 0.18181 0.21875 0.21740 qi − 0.085154 0.016982 0.33414 qi − − 0.37502 0.40037
x4 0.36842 −0.00001 0.21432 0.029810
+ ,-.
. " / ( |A| = (−1)3 × 0.36842 × . (−0.011020) × 0.14310 × 0.029810 = 1.7319 × 10−5 $ % b / ' # ! ( 0( 1 1 P b = (0.15792 . 0.15380 0.21431 0.17642)T ! 2 1 c = (0.15792 −0.011070 . T ˜ = (−7.9333 0.071625 −0.029527) )( x T 4.9593 1.9841 −0.99051) . 2!# ( ) ) r˜ = (2, 3, −3, 7)T × 10−5 ! ( /3 ) . r = (2.3951, 7.1948, −4.5999, 5.0390)T × 10−5
r˜
r˜ ! r = Ax ˜ − b " # $ ! %& '() * +# $ + P r = (−4.5999, 5.0390, 7.1948, 2.3951)T × 10−5
. cr = (4.5999, −9.8413, 23.926, −28.056)T × 10−5 ,
, ! . z = (0.066142, 0.040360, 0.015768, −0.0094116)T . ˜ ˜ x z # x ˜+z =x ˜ # " + ." x $$/ 0 1 $ . ˜= ˜ x (−7.9994, 4.9997, 1.9999, −0.99992)T
x = (−8, 5, 2, −1)T # . ! r = (4.7062 6.5713 5.0525 5.3850)T × 10−5 ." 2 $ 3$ 4 ! r # 5 ,$ # ˜ ˜ # x ˜ " # " " x 4 5 ! "5 , #
x ˜ Ax = b ! " # $ ! % x ˜ −x &
' & ( ' & ')#
* % " ( x ∈ Rn "
'& A ∈ Rn,n #
$ ( x ( x ∈ R
" % +* , &n
a)
x ≥ 0 x, x = 0 x = 0;
b) c)
cx = |c| · x c ∈ R x; x + y ≤ x + y x, y .3 1.
./#001 ./#021 ./#01
,
x∞ := max |xk |, x2 :=
k
n
12 x2k
k=1
x1 :=
n
(L1 ).
|xk |,
!
k=1
"#$% & '%( (" ) * +, & $- (" x ∈ Rn $ .%% % √ 1 √ x2 ≤ x∞ ≤ x2 ≤ nx∞ , n 1 x1 ≤ x∞ ≤ x1 ≤ nx∞ , n √ 1 √ x1 ≤ x2 ≤ x1 ≤ nx2 . n
. A A ∈ Rn,n / '& - '%( (-0 a)
A ≥ 0 (" A, A = 0 (" A = 0;
b) c)
cA = |c| · A (" c ∈ R A; A + B ≤ A + B (" A, B ) %%;
d)
A · B ≤ A · B.
1 2
) %( '%( + ( (" 3-% -% 4 %#+ 5
|aik |,
6
|aik |,
*
7
AG := n · max |aik |, i,k
Az := max i
⎡ AF := ⎣
k=1
As := max k
n
n i=1
n
⎤ 12
a2ik ⎦ ,
/ #
i,k=1
) %%# '%( 1& 2 ("& 8 ) '%( - - (" 5
n n A · BG = n · max aij bjk ≤ n · max |aij | · |bjk | i,k i,k j=1 j=1 ≤ =
n · max i,k
n
{max |alm |} · {max |brs |}
j=1
r,s
l,m
n2 · {max |alm |} · {max |brs |} = AG · BG . r,s
l,m
! " A ∈ Rn,n # 1 AG ≤ Az,s ≤ AG ≤ nAz,s , n 1 AG ≤ AF ≤ AG ≤ nAF . n $ " % &
" !" ' & % !
( A ) & x% # Ax ≤ A x x ∈ Rn A ∈ Rn,n .
*+,-
. / AG Az ! x∞ ; AG As ! x1 ;
*+01*+02*+0+-
AG AF ! x2 .
/! " " 3 n n Ax∞ = max aik xk ≤ max |aik | · |xk | i i k=1 k=1 n [max |ars |] · [max |xl |] = AG · x∞ ≤ max i
k=1
r,s
l
4 ! &/ # 5 3" # & ⎡ ⎤1 n n 12 n n 2 2 n 2 2 ⎣ ⎦ Ax2 = aik xk ≤ aik xk i=1
=
i=1
k=1
n n i=1 k=1
12 a2ik
n k=1
k=1
12 x2k
= AF · x2 .
k=1
!" # $ " % & ' ()
() *" x = 0 + ("
& " "
,"
% A := max x=0
*" " & -
Ax = max Ax x x=1
./
" # $ " " " 00 "
%
x
! " # $ ! % & $ ! % ' " # !
( !
1 ! &% 2 ( # $ "
# x = 0 Ax ≥ 0 () A ∈ Rn,n
x > 0 3" max Ax/x ≥ x=0 0 1 % % ' A = 0 A = 0 (" 1 + '
A = 0
$
apq = 0 3) x 4 q 5
2 !" eq = 0' () Aeq = 0 3) *" Aeq /eq > 0 #$ ./ ' " 1 0 !" ( +
% 2 ( *" " cA := max cAx = max {|c| · Ax} = |c| · A. x=1
x=1
6 % () *" " (" A + B
:= ≤
max (A + B)x ≤ max {Ax + Bx}
x=1
x=1
max Ax + max Bx = A + B.
x=1
x=1
0 ! 4 ," % ' % A = 0
B = 0 !"
( 7 ! ()
A · B := ≤ ≤
max x=0
ABx = x
max
x = 0 Bx = 0
A(Bx) Bx Bx x
A(Bx) Bx · max Bx=0 x=0 x Bx Ay Bx · max = A · B. max y=0 y x=0 x max
!" # $ % & # '() ()" x = 0 " Ax = A · x
*+ , x∞ # A∞ () n A∞ := max Ax∞ = max max aik xk i x=1 x=1 k=1 n n = max max aik xk = max |aik | = Az . i i x=1 k=1
k=1
- & . /0 / i 1+" /
xk = (aik ) $/ * % & # )
2 " % () 3 # () x2 #)1 0 () A2 )# " /
4) $ / () 1
1
A2 := max Ax2 = max {(Ax)T (Ax)} 2 = max {xT AT Ax} 2 x2 =1
x2 =1
x2 =1
# $( / AT A ' 5() % " . /0 #)1 6 () Q(x) := xT (AT A)x ≥ 0 /0
x = 0 () 7. μi % AT A
() %" n 7% x1 , x2 , . . . , xn %
" ) - Rn μi ∈ R,
AT Axi = μi xi ,
μi ≥ 0;
8!
xTi xj = δij
x ∈ Rn
9 7% xi x=
n
!
ci x i
i=1
()
-0(() % 8! ⎛ ⎞ n T n xT AT Ax = ci xi AT A ⎝ cj xj ⎠ i=1
=
n i=1
T
ci xi
⎛ ⎝
j=1 n j=1
⎞
cj μj xj ⎠ =
n
c2i μi .
i=1
7. μi *1+ () " μ1 ≥ μ2 ≥ . . . ≥ μn ≥ 0
x2 = 1
n
c2i = 1
i=1
A2 = max
x2 =1
n
12
≤ max
c2i μi
x2 =1
i=1
μ1
n
12 c2i
=
√ μ1 .
i=1
√ μ1 x = x1 c1 = 1, c2 = . . . = cn = 0 ! √ A2 := max Ax2 = μ1 , "#$% x2 =1
μ1 & ! ' AT A ( )( A2 * + ,, ( ( )( '- +.( '- +. A λ1 , λ2 , . . . , λn ! ' A AT A = AA = A2 ( ! μi = λ2i ≥ 0 "#$% A2 = |λ1 |,
"##%
|λ1 | = max |λi |. i
+.( / A & ! λ1 ) +.(√ 0' A−1 - A * "#$% A−1 2 = ψ1 , ψ1 T & ! ' A−1 A−1 = (AAT )−1 ' C −1 ( .( ! ' C ψ1 .( ( ". '% ! . ' 1 AAT - AT A A−1 (AAT )A = AT A AAT AT A ! √ A−1 2 = 1/ μn , "#2% μn ( ! . ' 1 AT A 3 / - A−1 2 = 1/|λn |,
AT = A,
|λn | = min |λi |. i
"#4%
3 5 ( *- x ˜ 6 x 7 - +/ Ax = b 8 9 : ;( 5& ; '( r = A˜ x − b 3 z := x − x ˜ ( A x '- )( " <% 3'( z 5 / Az = −r b = Ax ≤ A x,
z = − A−1 r ≤ A−1 r
"2=%
z ˜ x − x r r = ≤ A A−1 =: κ(A) . x x b b
!
κ(A) := A A−1
! " # $ Ax = b $ % & A '() $ & κ(A) ( * % &($ '( ( κ(A) $ +, 1 ≤ I = AA−1 ≤ A A−1 = κ(A).
-(- , $ - .- ( r , ( ! / b '( ( 0 x ˜ 0 - '( ( - $ - .- ( - ( *1
! " #$% ! & ' ( )*+ x ∞ , A ∞ = A z ! ! , - . ! / A−1 1 0 168.40 −235.80 −771.75 875.82 C B 138.68 470.63 −528.07 C . B −101.04 A−1 = B C @ −50.588 69.434 188.13 −218.89 A 33.752 −41.659 −112.88 128.73 . . . −1 A ∞ = 2.3572 A ∞ = 2051.77 κ∞ (A) = 4836.4 ) x ∞ = 8 r ∞ = −5 7.1948 · 10 b ∞ = 0.21431 " #$% ˜ x − x ∞ ≤ 12.99 0 ˜ x − x ∞ = 0.0667 !
. $ - (, . '(2 3 aik bi # $ $ . &- / $ ( $ . , + . ( $ +4 ( " x *, " x '() 5 6 7 (! - 8 δx " x ( Ax = b , % & A $ δA / b $ δb *9 ( δA δb - / , % & A + δA :- ( x + δx ( ( " ( (A + δA)(x + δx) = (b + δb)
0 $ ;- (
Ax + A δx + δAx + δA δx = b + δb,
* Ax = b * *
A δx = δx =
δb − δAx − δA δx, A−1 {δb − δAx − δA δx}.
δx ≤ ≤
A−1 δb − δAx − δA δx A−1 {δb + δA x + δA δx}
(1 − A−1 δA)δx ≤ A−1 {δb + δA x}.
!"# $ δA % # A−1 δA < 1 & ' " (
δx) A−1 {δb + δA x}. δx ≤ 1 − A−1 δA ' ' " ' "
Ax = b ' b = Ax ≤ A x
δx x
≤
A−1 1 − A−1 δA
≤
A−1 A 1 − A−1 δA
!
!
x ≥ b/A, δb + δA x
"
δb δA + b A
" .
* A−1 δA = κ(A)δA/A < 1 + ' " ! δx κ(A) δA δb ≤ + x A b 1 − κ(A) δA A
,
& - " κ(A) -." / A 0$1# +23 % 4$ x ' ( δA δb ' ' 5 2% 6 -7" ' " 6 d8 " 0 2% %$ ' ' # %2 ' 0$1
δA/A ≈ 5 · 10−d,
δb/b ≈ 5 · 10−d
9 - " κ(A) ≈ 10α 5 · 10α−d 1# ' , 7 ' "
δx/x ≤ 10α−d+1 .
* " +23 % "
Ax = b d κ(A) ≈ 10 α
d−α−1
x ˜
! " # $ δx
% & x # '
( ) *+, + +, & ' , +
. Ax = b
! ! ! 0.99 0.98
A=
0.98 0.97
,
b=
1.97 1.95
,
x=
1 1
.
A !""# !"$# . % &'
( ) A . . κ(A) = |λ |/|λ | = 1.96005/0.000051019 = 38418 = 3.8 · 10 ! * + + , , + +- . d = 5- α = 4 ! / 0-
& !(A + δA)(x + δx) = (b + δb) ! 1
4
2
A + δA =
1&
0.990005 0.979996
0.979996 0.970004
,
b + δb =
1.969967 1.950035
!
!
. 2 / .!34# 5 !
δA . . 8.531 · 10 - A = 1.960- δb = 4.810 · 10 - b = 2.772 + . x + δx =
−6
1.8072 0.18452
2
,
2
0.8072 −0.81548
. δx =
−5
2
. =
2
4
δx 2 3.842 · 10 ≤ {4.353 · 10−6 + 1.735 · 10−5 } = 1.001,
x 2 1 − 0.1672 .
δx 2 / x 2 = 0.8114
/ /
!
! / & ' 0 %1
23 + 0 ( +
3
4
5
2 0 6 0
P (A + δA) = L˜ R˜ L˜ ˜ * 3 R 4 5 & δA 7 !
. - / / δb 8 5
'
5 92 :; 2 ( < ( => $ δA δb /
'
23 & *+, & 5 +, 23 ' &
!!" #! $ " % ! "!
" ! " ! & ! ' #$ $
() ! !*
$ ' #! # " + ,
- ( , ! % " " . % "" ! / " /
$ 0$ % " d( !!
"! ! $ . % " α < d − 1 , +" 1
(d − α − 1) "! !! !!% ) ! 0 ,( ! $ 0
! '! 2 !!
3 . ' / ! κ(A) = 2.82 · 103 #! 1$ ! " x ˜ ! "! !! % , !
1 !! 1 !! 4 " "" , ! x ˜ ( # $ " ! % !! $% , # 0 !! % / / ! κ(A) ( ! " 50 0 A $! 6
0 AT A 7" " - ! ! 8 9 0 "% - $! % " 0
" & ( 1
# κ(A) !
:4! 2;% ) 22% < =% / >
5 0! ! ! * " " 1 $ ! ' #$ $ & ( 1 1 ! ? )!! ! ! * "% 0 ( "" ! 3! ! % ' / ! @= @@ ?
!! ! ! " $" A " # &! " & ""
B / C " D A Ax = b *"" % 0 E 6 ' * # % 6 ! !
6 *"" A D A ∈ Rn,n 0 E % !! ( F ) " 0 E G !! ! n n Q(x) := xT Ax = aik xi xk ≥ 0 # !! x ∈ Rn , 2 i=1 k=1
=
0
# x = 0.
A ∈ Rn,n
aii > 0 i = 1, 2, . . . , n; a2ik < aii akk i = k; i, k = 1, 2, . . . n;
k
max |aij | = akk . i,j
x = 0 ! " x = ei i# $ Q(x) = aii > 0 % x = ξei +ek & ξ ∈ R & i = k & ' (" Q(x) aii ξ 2 + 2aik ξ + akk > 0 ) ξ ∈ R ' aii ξ 2 + 2aik ξ + akk = 0 $ *+ ξ & $ " 4a2ik − 4aii akk < 0& , "" " - & +- . /"
& 0" "
1 ) 2 3"" # . / " " . 4 $ ' (" !"" 5 ) a11 > 0 "& % A ! 67 2 ( 8" & x1 & " % 5 %9 n n n Q(x) = a11 x21 + 2 ai1 x1 xi + aik xi xk i=2
=
=
i=1
l11
=
(1)
=
aik
i=2 k=2
2 $ n # n n √ ai1 ai1 a1k aik − xi xk a11 x1 + xi + √ a11 a11 i=2 i=2 k=2 2 2 n n n n (1) li1 xi + aik xi xk = li1 xi + Q(1) (x(1) ) i=2 k=2
6
i=1
√ ai1 ai1 a11 ; li1 = √ = , i = 2, 3, . . . , n; a11 l11 ai1 a1k aik − = aik − li1 lk1 , i, k = 2, 3, . . . , n. a11
:
Q(1) (x(1) ) ' (" (n − 1) ; x2 , x3 , . . . , xn " <=# (1) aik :& " - 0 " " " "
" > " a11 ! + . / 3"
!
(1)
A
A = (aik ) a11 > 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 < i=1 k=1
k=1
i=k
,-
. !" % & %
( 7 # ' 5 = " > ! ! &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;<# , 4))# "; 4) & $ # / A = LLT Ax = b #/ LLT x = b
#
L(LT x) = b.
==
! ) 9# c = L x ) >?$ Ax = b #) # $ ( ) # # # T
1. A = LLT 2. Lc = b 3. LT x = c
:4;<# @#&5#/ → c) '/ → x)
=
A/& :4;<# # ($ # "4) n B#; &# /$ ) ) "%;>#) /# C / 7; # # ($ ## D# @# <# # 2# # 4))# #
(k)
aij k ! "
# (n − k) $ (1 + 2 + . . . + (n − k)) = 1 (n − k + 1)(n − k) %" $ & ' "(!) 2
* $ n #
{(n − 1) + (n − 2) + . . . + 1} 1 + {n(n − 1) + (n − 1)(n − 2) + . . . + 2 · 1} 2 ! " 1 1 1 1 n(n − 1) + n(n − 1)(2n − 1) + n(n − 1) = 2 2 6 2 1 3 2 (n + 3n − 4n) = 6 +% ,
- & ! ." /
lii = 1 & 1 ZV = ZR = (n2 + n) 2 %"$ +% & 01 $ n
* $ ' "( T ZLL
=
Z =
1 3 3 2 1 n + n + n = 0(n3 ) 6 2 3
2
+% 3. 14 n 5 - 67
4 )
01
22 $
8 aik $ 5 5 $& . k = 1, 2, . . . , n : akk ≤ 0 : 9:+, √ lkk = akk . i = k + 1, k + 2, . . . , n : lik = aik /lkk . j = k + 1, k + 2, . . . , i : aij = aij − lik × ljk
26
. i = 1, 2, . . . , n : s = bi . j = 1, 2, . . . , i − 1 : s = s − lij × cj ci = s/lii
2;
i = n, n − 1, . . . , 1 : s = ci k = i + 1, i + 2, . . . , n : s = s − lki × xk xi = s/lii
aik aik !! "#$ lik % & L ' A ! ( ( ) l a ! *! (#$ & + ,& b c *! ( -%((& x c *! ( (( ' b -%( x ($ . #$ /#$ 0 ( #$ 1! ! !$ (( $ 2$ (&3 4 ! A L ( !( ( ) ! (5#$ ( ( ( aik * (#$ ( r6 7 5 ( ) r = 12 i(i − 1) + k '5#$ 8! S = 12 n(n + 1) ( 4 ,#$ ! '5#$ A:
a11
a21
a22
a31
a32
a33
a41
a42
a43
a44
· · ·
! "#$ % Ax = b 1 1 0 0 5 7 3 C C B B b=@ 0 A A = @ 7 11 2 A , 1 3 2 6 0
& %
' " " & ! 1.2000 −2.1999 (1) A = , A(2) = (0.16680) −2.1999 4.2001 ( " " L $" c & $)& *# + x ˜ 1 0 1 0 1 0 −18.984 0 2.2361 0 0 C B C B C B ˜ = @ 10.991 A . L = @ 3.1305 0 1.0954 0 A, c = @ A, x 5.9952 2.4485 1.3416 −2.0083 0.40841
& & , " r = (2.6, 3.4, 1.2)T ·10−3 - & % . " & κ(A) = 1.50 · 103 * -" . T −3 z = (−15.99, 8.99, 4.80) · 10 & * % )
" (+ x = (−19, 11, 6)T %& * + x ˜ &
) .
A aik ! " #
$
m ! % A ∈ Rn,n
& ' m < n aik = 0 i k |i − k| > 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 . .& < lkk m = lik 12 m(m + 1) 8 & .& 7&!8 ' # % > n # m 6 n < 8 12 nm(m + 3) > > n < # m 9
! " #
n(m + 1)
! ! " # ! " # $ ! n % ! & ' ( ) * ) m
Z ≤
1 nm(m + 3) + 2n(m + 1) = O(nm2 ) 2
+,-./0
1 2 ! ) * # ' 3 " " ,- ! 4 n 5 (m + 1) 2 ! 6 ' # 7 ! A 2 # ' i 5 A i 5 4 6 6! A (m+1) 2 4 # ( ' aik A max(i−m, 1) ≤ k ≤ i (k −i+m+1) 2 4 6 6 4 ( #8! ! ! # " ,- ( 2# aik 6 * 6 ! 4 ! 9 & 5! ! A = LLT ) *
! n ) m 2 ! " ,- : k = 1, 2, . . . , n : ak,m+1 ≤ 0 : 2;< √ lk,m+1 = ak,m+1 p = min(k + m, n) i = k + 1, k + 2, . . . , p : li,k−i+m+1 = ai,k−i+m+1 /lk,m+1 j = k + 1, k + 2, . . . , i : ai,j−i+m+1 = ai,j−i+m+1 − li,k−i+m+1 × lj,k−j+m+1
A i ! " # xi−1 , xi xi+1 " $ %# & ' ( ' ' ( n = 5 " # x1 a1 c2
x2 b1 a2 c3
x3 b2 a3 c4
x4
b3 a4 c5
x5
b4 a5
1 d1 d2 d3 d4 d5
)*++,-
. ! ( / ( 0 1( A $ $ 2 # A = LR(
2 ( L 3 # # R ' # . #4 1 # # ⎞ ⎛ ⎛ ⎞ ⎛ ⎞ m1 r1 1 a1 b 1 ⎟ ⎜ ⎜ c2 a 2 b 2 ⎟ ⎜ l1 1 ⎟ m2 r2 ⎟ ⎜ ⎜ ⎟ ⎜ ⎟ ⎜ ⎜ ⎟ ⎜ ⎟ ⎟, c3 a 3 b 3 m3 r3 l2 1 ⎟·⎜ ⎜ ⎟=⎜ ⎟ ⎝ ⎝ ⎠ ⎝ ⎠ c4 a 4 b 4 m4 r4 ⎠ l3 1 c5 a 5 m5 l4 1 )*+++ # 4/ li , mi , ri & !
5 c2 c3 c4 c5
= l 1 m1 , = l 2 m2 , = l 3 m3 , = l 4 m4 ,
a1 a2 a3 a4 a5
= m1 , = l1 r1 + m2 , = l2 r2 + m3 , = l3 r3 + m4 , = l4 r4 + m5 .
b1 b2 b3 b4
= r1 , = r2 , = r3 , = r4 ,
)*++*-
)*++*- " # # ' m1 6 r1 ( l1 ( m2 6 r2 ( l2 ( m3 ; . . . ; r4 ( l4 ( m5 ri = bi 1 i ( 0
& A )*++,- 1 n : m 1 = a1
1 i = 1, 2, . . . , n − 1 : li = ci+1 /mi mi+1 = ai+1 − li × bi
)*++7-
Ly = d Rx = y y1 = d1 i = 2, 3, . . . , n : yi = di − li−1 × yi−1
!""#$
xn = yn /mn i = n − 1, n − 2, . . . , 1 : xi = (yi − bi × xi+1 )/mi
!""$
% & '( ) * )+ , - . / ! 0 . '(
Z
= 2(n − 1) + (n − 1) + 1 + 2(n − 1) = 5n − 4 = O(n)
!"" $
.. 0 1! / + ) * ( ! 2 )+ , 0 ! - &. /* !""3$ 4 /.5 )! , & % 65 a1 c2 4! - 7 (+ α := |a1 | + |b1 |,
β := |c2 | + |a2 | + |b2 |.
!""8$
9 |a1 |/α ≥ |c2 |/β 2 a1 &2 0 ! : 9 / "2;$ , %2 + 4 ! 1 % (2 )(+ <! ! r1 := a1 , s1 := b1 , t1 := 0, f1 := d1 9 a1 & : u := c2 , v := a2 , w := b2 , z := d2 !""=$ ! r1 := c2 , s1 := a2 , t1 := b2 , f1 := d2 9 c2 & : u := a1 , v := b1 , w := 0, z := d1 6 !""3$ ) x1 r1 u
x2 s1 v c3
x3 t1 w a3 c4
x4
b3 a4 c5
x5
b4 a5
1 f1 z d3 d4 d5
!"">$
x1 r1 l1
x2 s1 a2 c3
x3 t1 b2 a3 c4
x4
b3 a4 c5
x5
b4 a5
1 f1 d2 d3 d4 d5
l1 := u/r1 ;
a2 := v − l1 s1 ,
b2 := w − l1 t1 ,
d2 := z − l1 f1 .
! " # $ % &' ( ) * + % (n − 1), ! bn = 0 - + . % x1 r1 l1
x2 s1 r2 l2
x3 t1 s2 r3 l3
x4
x5
t2 s2 r4 l4
t3 s4 r5
1 f1 f2 f3 f4 f5
* ',/ % * 0 - 1 # % * (! ) 0 & 2 % i = 1, 2, . . . , n − 1 : α = |ai | + |bi |; β = |ci+1 | + |ai+1 | + |bi+1 | % |ai |/α ≥ |ci+1 |/β : ri = ai ; si = bi ; ti = 0; fi = di ; u = ci+1 ; v = ai+1 ; w = bi+1 ; z = di+1 ; ri = ci+1 ; si = ai+1 ; ti = bi+1 ; fi = di+1 ; u = ai ; v = bi ; w = 0; z = di li = u/ri ; ai+1 = v − li × si bi+1 = w − li × ti ; di+1 = z − li × fi rn = an ; fn = dn
3
4 5 3 5 6 7 - 8 9 ai ! bi ! ci ! di * , -& ! +: 3 % 0 2 ri = ai ! si = bi ! li = ci+1 ! fi = di + 1 1 1 ! 3 + - %
xi xn = fn /rn xn−1 = (fn−1 − sn−1 × xn )/rn−1 i = n − 2, n − 3, . . . , 1 : xi = (fi − si × xi+1 − ti × xi+2 )/ri
! " #! $ %&' () n * + " ,"
Z
= 5(n − 1) + (n − 1) + 3(n − 1) = 9(n − 1) = O(n).
- . $ " !! / ," 0 1 L 2 P A = LR $
/
R 1/ $ 3 % " " 4 1
" % . $ 0' "
() 5
6
$! 7 - ! 6!
7 / !$ % . 7 ,
" % ! " / 4' 8 ! 9$ $$ % 6
7, % :
/ % 7; $ / %7
8
/ ; " !$ * ; $ 2
* $ % 7,
8 7( '</ %$ , $ / ! = '< . ! $ ,
* 4 $> 27 6! 7 ' > '< !1 %7
, * " 6
) " < > ? " " 6
@
!/ $> 7 "$ 6 ? 3 AA B8 CDE 4 % " @' !
. 7 % F B% A/ > C/ 8 CD/ 8 CC/ = C/ = CA/ CG/ ( CA / @ HH/ 0 C/ # HH/ ". CAE - = $ )! % 7 4F *$ 0' % ( <7% !
.
$ / $ > B CE
! " # $ % & '#( ) * + ,) " %% - ../$ % 0* $ $ $
' 1 2# ) # !) ) * + 2#
! % ! 3
# ) * 45 3 ) ) 1# % $ ) LR 6 -7 . / % * ) ! P × Q " '## 8 * 9 , ' % ,& % $ ) ) * % %% ) $ 6, % ) 5 + ! * ' mb × nb 1 6 * 1 % '# ) % " * + ) 5
2 × 3" 12 × 12 1 %%* 0*0 %% * + ! % % 1 : #
'# * + 3 %% ;
" $ # 1 * + %% < ' " = > 6 × 4 1 * + < $ 5* '
+ ! % # * 45 P = Q = 1
'# ' 5 * 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11
0 3 0 3 0 3 0 3 0 3 0 3
1 4 1 4 1 4 1 4 1 4 1 4
2 5 2 5 2 5 2 5 2 5 2 5
0 3 0 3 0 3 0 3 0 3 0 3
1 4 1 4 1 4 1 4 1 4 1 4
2 5 2 5 2 5 2 5 2 5 2 5
0 3 0 3 0 3 0 3 0 3 0 3
1 4 1 4 1 4 1 4 1 4 1 4
2 5 2 5 2 5 2 5 2 5 2 5
0 3 0 3 0 3 0 3 0 3 0 3
1 4 1 4 1 4 1 4 1 4 1 4
2 5 2 5 2 5 2 5 2 5 2 5
0 3 6 9 1 4 7 10 2 5 8 11 0 2 4 6 8 10 1 3 5 7 9 11
P0
P1
P2
P3
P4
P5
! " # $% &
R0
A11
R0
A12
L0
R11 L11
R12
L21
˜22 A
L0 A21
A22
! " # $% & $ '
(
# A ∈ Rn,n n nb m = n/nb P = Q P m )* + k , ' # - . ' /
$
0 - . A k−1 , k , # )* A(k) k #
- . 1% LR $ # $# $ # 0 L11 R11 R12 A11 A12 = A(k) = 2)3)45 A21 A22 0 R22 L21 L22 $ # L11 R12 L11 R11 . = L21 R11 L21 R12 + L22 R22 A11 ∈ Rnb ,nb A22 ∈ Rn−knb ,n−knb ' 6 1% k 2)3)45 $ 7 8 235 A11 = L11 R11 −→ A11 2)5 0& RT11 LT21 = AT21 L21 −→ A21 2*5 0& L11 R12 = A12 R12 −→ A12 295 : A22 − L21 R12 −→ A22 6 A22 #
7 A(k+1)
! "!"! # $ % & '( ! # & ) ' L0 ! "!* ($ ! + ( , -&& '( A(k) ! # .(( ( , -&& & / '( 0 $ , -&& .((10 &&! ) .'(12 3(& ( ) .(( ! +4 ) ' 5 & " (n − (k − 1)nb ) × nb 1.(( 1 ! L11 nb × (n − (k − 1)nb )1.(( 1)6 ' 5 & *! '( L21 $6 ) '( R12 $ ' A22 ! 7 6 ) ' $ % 8(&& 1 ( 3 $ .(( ! 2 9:( ;<= $ (& & & . 6 3
(&& & 3 ' . ! 3 & . ( 1& & > ,? @<A. .(( $ ( B nb = 8 3 & 16 × 321.((3 ( ;; C '( & > 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 .
"!"<
k = 2, 3, . . . , n + 1 : (1) i = 2, 3, . . . , n : aik = aik − li1 × a1k
! " # $ " (n − 1) % & k & ' a1k & l&( $ ( " )* A (1) li1
ai1 ( aik
" aik $+ $ ,- ' ! . /0&. $+ % - & '# ,- $+ ,- $& . " 1 2 . 3 $ - 45 ,- . 6 70 , - . 8 6" 6-$ 9 :$- xi n xi = ci − rik xk /rii , i = n, n − 1, . . . , 1, k=i+1
"-$ '- - ; )* rik i& ! ' . " 9--<- $ %7 6 $ - . / = 6-$ & > 9 :$- xi xi & i& ? " R 1 ? ; ,- 8 3 % 5 6-$ "-$ i = n, n − 1, . . . , 2 : xi = ci /rii j = 1, 2, . . . , i − 1 : x1 = c1 /r11
cj = cj − xi × rji
@
. @ 45 ,- " (n − 1) 1 $ 3 " ,- $ 45 - )>- /0&. " / % $+ :$- 12 A =" "B 0 p& % p ≥ 2 :$- xp
/ . C
a11 = 0 x1
x2
x3
x4
1
1
(1) a12
(1) a13
(1) a14
a15
0
a22
a23
a24
(1)
a25
0
(1) a32 (1) a42
(1) a33 (1) a43
(1) a34 (1) a44
(1) a35 (1) a45
(1)
0
(1)
(1) (1)
! " (1)
a1k = a1k /a11 ,
k = 2, 3, . . . , n + 1,
(1)
(1)
aik = aik − ai1 · a1k , i = 2, 3, . . . , n; k = 2, 3, . . . , n + 1. (p−1)
app
#$
= 0 % & p'
p ≥ 2 (p)
(p−1)
(p)
(p−1)
apk = apk aik = aik
(p−1)
/app
,
(p−1)
− aip
k = p + 1, p + 2, . . . , n + 1, (p)
· apk , i = 1, 2, . . . , p − 1, p + 1, . . . , n; k = p + 1, p + 2, . . . , n + 1.
#
( ) !*
+, - * (n)
xk = ak,n+1 ,
k = 1, 2, . . . , n.
. % / 0 * 1&* ,
1 2 0.5n3 ,
1' % /3' 4$5 03 %* ' 2 ( 6 * 78 n , 0 1 1 /3'9 '% *
%* '
* & * n * : /3' ; *83 ( # + i = p (p) ,
8 < apk = 0 , 3 < & p = 1, 2, . . . , n : & k = p + 1, p + 2, . . . , n + 1 : h = apk /app & i = 1, 2, . . . , n : aik = aik − h × aip apk = h & k = 1, 2, . . . , n : xk = ak,n+1
#
# )
=
, = p' > , 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,
)*!+,
; < 5 0 2 5 2 ; - / ! $ $ . 0 n n = 2m, m ∈ N∗ ! # i ∈ N∗ 2 < i < n ! ci−1 xi−2 + ai−1 xi−1 + bi−1 xi = di−1 ci xi−1 + ai xi + bi xi+1 = di ci+1 xi + ai+1 xi+1 + bi+1 xi+2 = di+1
xi−1 xi+1 (−ci /ai−1 )0 (−bi /ai+1 )0 ! = " ! ci−1 ci bi−1 ci bi ci+1 bi bi+1 xi − − xi−2 + − + ai − xi+2 ai−1 ai−1 ai+1 ai+1 )*!+3, di−1 ci bi di+1 = − + di − , i = 2, 4, . . . , n. ai−1 ai+1 )*!+3, i = 2 i = n % / c1 = cn+1 = bn = bn+1 = dn+1 = 0,
an+1 = 1.
)*!+4,
& . >6 ; ' i ? ⎫ (1) ⎪ ci := −ci−1 ci /ai−1 ⎪ ⎪ ⎪ ⎪ ⎪ (1) ai := −bi−1 ci /ai−1 + ai − bi ci+1 /ai+1 ⎬ i = 2, 4, . . . , n. )*!+9, (1) ⎪ ⎪ bi := −bi bi+1 /ai+1 ⎪ ⎪ ⎪ ⎪ (1) ⎭ di := −di−1 ci /ai−1 + di − bi di+1 /ai+1
n = 8 x1 a1 0
x2 b1 (1) a2 c3 (1) c4
x3
x4
0 a3 0
b2 b3 (1) a4 c5 (1) c6
x5
x6
x7
0 a5 0
b4 b5 (1) a6 c7 (1) c8
x8
1 d1 (1) d2 d3 (1) d4 d5 (1) d6 d7 (1) d8
(1)
(1)
0 a7 0
(1)
b6 b7 (1) a8
! ! "# $ ! ! %& '( ! #! # )* )* x1 , x3 , x5 , . . . ! ! * + $ '! * * , '( x2 , x4 , x6 , . . . ! * # + ! * ! m m = 4 x2 x4 x6 x8 1 (1)
b2
(1)
a4
b4
(1) c6
(1) a6
a2
(1) (1)
c4
(1)
d2 (1)
(1)
c8
(1)
d4 (1) b6
-
(1) d6
(1)
(1)
a8
d8
. + ! ! $ / 0 # '( 1 '! 2 3 ! ! * 4 5# ⎞ ⎞ ⎞ ⎞ ⎛ ⎛ ⎛ ⎛ c1 a1 b1 d1 ⎟ ⎟ ⎟ ⎟ ⎜ c3 ⎜ a3 ⎜ b3 ⎜ d3 ⎟ ⎟ ⎟ ⎟ ⎜ ⎜ ⎜ ⎜ ⎟ ⎟ ⎟ ⎟ ⎜ ⎜ ⎜ ⎜ (u) (u) c(u) := ⎜ c5 ⎟ , a(u) := ⎜ a5 ⎟ , b := ⎜ b5 ⎟ , d := ⎜ d5 ⎟ ∈ Rm+1 ⎟ ⎟ ⎟ ⎟ ⎜ ⎜ ⎜ ⎜ ⎠ ⎠ ⎠ ⎠ ⎝
⎝
⎝
⎝
cn+1 ⎛ c
(g)
⎜ ⎜ ⎜ := ⎜ ⎜ ⎝
an+1 c2 c4 c6
cn
⎞
⎛
⎟ ⎜ ⎟ ⎜ ⎟ ⎜ (g) ⎟ , a := ⎜ ⎟ ⎜ ⎠ ⎝
a2 a4 a6
an
bn+1 ⎞
⎛
⎟ ⎜ ⎟ ⎜ ⎟ (g) ⎜ ⎟ , b := ⎜ ⎟ ⎜ ⎠ ⎝
b2 b4 b6
bn
⎞
dn+1 ⎛
⎟ ⎜ ⎟ ⎜ ⎟ ⎜ (g) ⎟ , d := ⎜ ⎟ ⎜ ⎠ ⎝
d2 d4 d6
⎞ ⎟ ⎟ ⎟ ⎟ ∈ Rm . ⎟ ⎠
dn
* 1 6'3 0 *! ⊗ 1 % #1 0 " & +1 0 *! '! &1
1
r
:=
⎛ ⎜ ⎜ ⎜ ⎝
−1/a1 −1/a3
−1/an+1
q
:=
b(g) ⊗ r +1
⎛
⎞ ⎟ ⎟ ⎟ ∈ Rm+1 ; ⎠
⎜ ⎜ p := c(g) ⊗ r = ⎜ ⎝
⎛
⎞
⎜ ⎜ =⎜ ⎝
−b2 /a3 −b4 /a5
−c2 /a1 −c4 /a3
⎞ ⎟ ⎟ ⎟ ⎠
−cn /an−1
⎟ ⎟ ⎟ ∈ Rm . ⎠
−bn /an+1
⎛ (1) ⎞ ⎛ (1) ⎞ ⎛ (1) c2 a2 b2 ⎜ (1) ⎟ ⎜ (1) ⎟ ⎜ (1) ⎜ c4 ⎟ ⎜ a4 ⎟ ⎜ b4 ⎜ ⎜ ⎟ ⎟ c1 := ⎜ ⎜ ⎟ , a1 := ⎜ ⎟ , b1 := ⎜ ⎝ ⎠ ⎝ ⎠ ⎝ (1) (1) (1) cm am bm
⎞
⎛
⎜ ⎟ ⎜ ⎟ ⎟ , d1 := ⎜ ⎜ ⎟ ⎝ ⎠
(1)
d2 (1) d4
⎞ ⎟ ⎟ ⎟ ∈ Rm ⎟ ⎠
(1)
dm
! " c1 = c(u) ⊗ p ; (u) a1 = a(g) + b(u) ⊗ p + c+1 ⊗ q ; (u) b1 = b+1 ⊗ q ; (u) d1 = d(g) + d(u) ⊗ p + d+1 ⊗ q.
#
$ % &' m $ ! ( 8m ) 4m * + ( , 13m ' &' -) . ) ' /) 0 &' 1 &' %&12&' , 0 + x1 , x3 , . . . , xn−1 !, 3 x2 , x4 , . . . , xn $ 2 , . &' , &' a1 x1 + b1 x2 c2i+1 x2i + a2i+1 x2i+1 + b2i+1 x2i+2
= d1 = d2i+1 ,
i = 1, 2, . . . , m − 1.
$ , x2i+1 = (d2i+1 − c2i+1 x2i − b2i+1 x2i+2 )/a2i+1 ,
i = 0, 1, 2, . . . , m − 1,
45
1 c1 = 0 &' 2 &' x0 = xn+1 = xn+2 := 0 0 &' &' ! " 6 ( ' 1 1 x(g)
:=
(x0 , x2 , x4 , . . . , xn , xn+2 )T ∈ Rm+2 ,
x(u)
:=
(x1 , x3 , x5 , . . . , xn−1 , xn+1 )T ∈ Rm+1
$ 45 (g)
x(u) = (c(u) ⊗ x(g) + b(u) ⊗ x+1 − d(u) ) ⊗ r.
4
7 1 ) , &' 82 , (m+1) ( ,' )&'
x(g) 3(m + 1) 2(m + 1)
!"" 5m # $ % " & ' " 18m # ( m ) * ! ! '
+ , " ( " n = 2q , q ∈ N∗ !, q " " + , " " ! & xn - ! . ! ! * ! ! & - ' " / !" "" " 0 n = 2q " 18n # (" / ! 1 +2' " 345567 345587 345597 8n " : '
!, 449" 12 ;
" ( > ? ! ! ) " !@ ; / ! ! ! " /! ! " / ! ! 1
@ " * ! ! " " ! + ! A BBC $ ! ' D / " * ! !, " 0 " ; * ! ! ' : ! ! + , " " + ! D1 , " " " +2' " $ %
&" + , " " " " '
* ! * " " " ! ! ! 1 1 " 2 1 ! +" 1
* " !"" ! ! ; ( ' 'E F'
/ / A / B / B C ! " * ! ! LR') 345557 > A + RQ') *
! ! R Q ! - ! & " ! R Q
n = 8 ⎛ 1 ⎜ r2 1 ⎜ ⎜ r3 1 ⎜ ⎜ r4 1 r5 ⎜ R := ⎜ ⎜ 1 r6 ⎜ ⎜ 1 r7 ⎜ ⎝ 1 r8 1
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟, ⎟ ⎟ ⎟ ⎟ ⎠
⎛
q1 b 1 ⎜ q2 b2 ⎜ ⎜ q3 b3 ⎜ ⎜ q4 ⎜ Q := ⎜ ⎜ c5 q5 ⎜ ⎜ c6 q6 ⎜ ⎝ c7 q7 c8 q8
⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟. ⎟ ⎟ ⎟ ⎟ ⎠
A = RQ ! "
#
$ % R " & % Q' q1 = a1 ; r2 q1 = c2 , r3 q2 = c3 , r4 q3 = c4 ,
r2 b1 + q2 = a2 ; r3 b2 + q3 = a3 ; r4 b3 + q4 + r5 c5 = a4 ;
r5 q5 q5 + r6 c6 = a5 , r6 q6 q6 + r7 c7 = a6 , r7 q7 q7 + r8 c8 = a7 , r8 q8 q8 = a8 .
= b4 ; = b5 ; = b6 ; = b7 ;
(
( ) % * # % +, q1 - r2 - q2 - r3 - q3 - r4 %. - !. / q8 - r8 - q7 - r7 - q6 - r6 q5 - r5 0 &
#
1 q4 ! & RQ23 #
%
- n = 2m, m ∈ N∗ - ! ! ' q1 = a1
" i = 2, 3, . . . , m : ri = ci /qi−1 qi = ai − ri × bi−1
qn = an
" i = n − 1, n − 2, . . . , m + 1 : ri+1 = bi /qi+1 qi = ai − ri+1 × ci+1 rm+1 = bm /qm+1 qm = qm − cm+1 × rm+1
4
5
!
" # " " $" % "" &" " qm ' rm+1 ( n = 2m + 1, m ∈ N∗ ) RQ*$" " + , + - m (m + 1) " R Q . /0 12 34 RQ*$" " + " 5 RQ*$" 4 6++ 7 8 5 M *5 /9 9 2 RQ*$" : (n − 1) 5" 7") # ++ 7 + +: LR*$" # ; RQ*$" " 5 4 A ;" *
6 + Ax = d RQx = d <= x )
"= >6 + Ry = d,
Qx = y.
' > ) 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 " + + > !
" <= " m* ;" Qx = y "
A
xm = ym /qm
i = m − 1, m − 2, . . . , 1 : xi = (yi − bi × xi+1 )/qi
i = m + 1, m + 2, . . . , n : xi = (yi − ci × xi−1 )/qi
<= >6 + + : * !
+ n : (2n − 2) 5" 7"* ) # " +: 9 * ) ;@* #" + !""" " + ) 3= $" + *
-7 $+ 347+ !""" +
! " # $ %& RQ' &( ) * + , - + ./ *% 0 *% 0 ! " & 1 ' $ # * & /& & ! 2 ( % * + * 3 2 * ! 4 /5 * . + , & * * 6 ! 7 89:* ; " * 3 <) ! " / n = 2m, m ∈ N∗ 4 ! 1 * # + , 8=!>>; + 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; ; -< .< 1 "# $%& . $=& 3 , 1 - > 9 - 9?4 "> ), 6; "' $%, - 1 ? @ "# $%,
0- A 2 3 -< 5 (; @ 6 ! # & & ; B C - 9
Zj 5 (@ Uj 6 Rj .< 6 Rj (@ Uj = 0V 0 (! (;
5 1 9 B # " +, 6 # ; 5 0 + (; D # <
E U1 = 10V, U2 = −15V, U3 = 20V, U4 = U5 = U6 = 0V
6 ! R1 = R2 = · · · = R6 = 10Ω.
> : 7 T = (tij ) ∈ R4,6 -& -< 8 A Ki #
DZj E −1 9
+1 & -< # ; F ⎛ ⎞ 1 0 −1 −1 0 0 ⎜ 0 −1 0 1 0 1 ⎟ ⎟. T =⎜ ⎝ −1 1 0 0 1 0 ⎠ 0 0 1 0 −1 −1 1 : 1 7 6 ! - F R−1 := diag(R1−1 , · · · , R6−1 ) = diag(0.1, · · · , 0.1), R−1 ∈ R6,6 .
U1 R1
K1 s ?U3
6 R4
K3
U2 s
R2
? s
R3
R6
sK 4
K2
R5
! " # Pj Kj $ % & ' ( ! ! " ! B = T · R−1 · T T ,
)* + ! , K4 # , - , ' ( B % & ! ⎛ ⎞ 0.3 −0.1 −0.1 A = ⎝ −0.1 0.3 −0.1 ⎠ . −0.1 −0.1 0.3 ' U := (U1 , . . . , U6 )T ! b = −T R−1 U ! , . b = (1.0, −1.5, 2.5)T .
/ , , 0 !% / ! #! 0 1 %+% & !2 3 ! ! " % & ' ( " , 4 5 5 ) ! %+% ! % & 3 ! ! " # P1 = 7.5V P2 = 1.25V P3 = 11.25V 6
+ ! # P4 = 0V % 7 ,! Uj )* 0 ! ! " %
! "# $%&
'( ) % # % # ( *( + Δp , -. l / 8ηl Δp = 4 q. πr / r ,
, 0 η
. # q
/ 1 ( 2( + $ " ( ( 3 4 % 0 + +( 5 )//( *(6 / " , , / (
0
$ ri 0 li 0 qi ki , i = 1, 2, . . . , 80 ,
0 -.0 1 7 + 8 i , 0 / ki :=
8ηli . πri4
9 )//( *(6 # + 0 # + :
9 "#( # " / ( / /
9 ( )4 4
)/1#
9 +/ ( ;
q1 = q8 (
3
$ " 0 0
( 5 $ " /
P "( 8 $ " " . 0 / ! 0
/# # ( ) ! "# $% < + q1 = q8 %
)" $= + / ! "#
;/ qi & q1 −
q2 −
q3 q3 −
q4 − q4
(k1 + k8 )q1 + k2 q2 k2 q2 − k3 q3 − k4 q4
q5
− k5 q5 + k5 q5
−
q6 −
q7
− k7 q7 k6 q6 − k7 q7
= = = = = = =
0 0 0 P 0 0 0
/ P
%
( #
9 P = 350 0000 η = 0.0150 ri ≡ r = 0.06 li = (2, 21, 3, 4, 6, 10, 6, 34) . $= ! 4) % ( " + $ 3/ & q1 = q8 = 2.9040 q2 = 0.67680 q3 = 2.2270 q4 = 0.97180 q5 = 1.2550 q6 = 0.36440 q7 = 0.6074(
! " # $# % &
' ( " ' ( ) ## # % *( +(, ## (
f¯ = 4N
f¯ = 9N
m ! j " 2j − 3 = m #$
% & # " ' !! ! (! Fx Fy ) & # !! ! (! * * cos ϕ sin ϕ ! ϕ + ! (! % √ , ( ϕ = π/4 ! #- t := sin π/4 = cos π/4 = 1/ 2 " # # ! . / # ! % ! 0 ! & # 1 ! & % & # ! 2 !! !! 3
" 1 & fi 4 i5 & ! " 6 - f7 7! −tf1 + f4 = 0 ! .−tf1 − f3 = 0 ! f2 − tf5 − f6 = 0 ! 8f3 + tf5 − 4 = 0 ! −f4 − tf5 + tf8 = 0 ! 9−tf5 − f7 − tf8 = 0 ! −f6 + f9 = 0 ! /=0 f7 − 9 & ! −tf8 − f9 = 0 f7
" & :* "
; Af˜ = b ⎞ ⎛ −t 0 0 1 0 0 0 0 ⎜ −t 0 −1 0 0 0 0 0 ⎟ ⎟ ⎜ ⎜ 0 1 0 0 −t −1 0 0 ⎟ ⎟ ⎜ ⎟ ⎜ 1 0 t 0 0 0 ⎟ ⎜ 0 0 A = ⎜ ⎟ ⎜ 0 0 0 −1 −t 0 t 0 ⎟ ⎟ ⎜ ⎜ 0 0 0 0 −t 0 −t 0 ⎟ ⎟ ⎜ ⎝ 0 0 0 0 0 −1 0 1 ⎠ 0 0 0 0 0 0 −t −1 T ˜ f = (f1 , f2 , f3 , f4 , f5 , f6 , f8 , f9 ) b =
(0, 0, 0, 4, 0, 9, 0, 0)T .
% < A , m = 3 % :* "5 (! = = & f = (−8.014, 5.667, 5.667, −5.667, −2.357, 7.333, 9, −10.37, 7.333)T .
% f
f7 & !
! " " # $ % &'( ) * " +, -. /)0) % 1 $# 2$ * % #. 3 $1 % 0! 45 3
6$ ! 45 &7$*. 8. / ) % 1 * ' ! &! $ 9 $1 93 93! )
" 2$
# : # 00! + ,) % ( 3 . . " &7. ;.$# + , ) 2$2$ &7$2$ + &7$&7$<.) , + , ( + , " 8 # $ 6 ) = = + ,) * 4$ ( ( 9 +
,)
; #5 + , " " # 45 3
6 ( &7 6
.$: &7 17 8>7)
2x1 − 4x2 + 6x3 − 2x4
=
3
3x1 − 6x2 + 10x3 − 4x4
=
−2
x1 + 3x2 + 13x3 − 6x4
=
3
5x2 + 11x3 − 6x4
=
−5.
LR
6.22x1 + 1.42x2 − 1.72x3 + 1.91x4
=
7.53
1.44x1 + 5.33x2 + 1.11x3 − 1.82x4
=
6.06
1.59x1 − 1.23x2 − 5.24x3 − 1.42x4
=
−8.05
1.75x1 − 1.69x2 + 1.57x3 + 6.55x4
=
8.10
! ! &
! " #$# %
˛
" ˛ ˛ 0.596 0.497 0.263 ˛ ˛ ˛ ˛ ˛ 3.21 1.39 ˛ . ˛ 4.07 ˛ ˛ ˛ 0.297 0.402 0.516 ˛
' ( " ! ! ) *% + ' + % & , !- . ( / " + %# 01 "& 2 % ( ! - " ! + & "' 3! " % 4- + 1 &
10x1 + 14x2 + 11x3
=
1
13x1 − 66x2 + 14x3
=
1
11x1 − 13x2 + 12x3
=
1
+ 1 " #$# % ! & 5 P ! L R " % #$ 6 & 7! A #$ ." 6
! " 1 +( AB F ≤ A F B F ." 6&
+)! - ." 6 4 1" &
L1 !
" # $ %
&
a)
κ(AB) ≤ κ(A)κ(B) #
'
b)
κ(cA) = κ(A) #
c ∈ R;
c)
κ2 (Q) = 1 #
Q;
2
d)
κ2 (A) ≤ κF (A) ≤ κG (A) ≤ n κ∞ (A);
e)
κ2 (QA) = κ2 (A),
Q .
( ) * * +, - A
). ( /+ , 0 * #
1
2 3 5x1 + 7x2 + 6x3 + 5x4
=
12
7x1 + 10x2 + 8x3 + 7x4
=
19
6x1 + 8x2 + 10x3 + 9x4
=
17
5x1 + 7x2 + 9x3 + 10x4
=
25
# / 4 $ , A 5 , 6 7 8
* 1 0 4 2 −1 0 −2 C B B 3 −2 4 C B −2 B −1 A=B C, B = B @ 4 @ 0 −2 4 −3 A −6 −2 4 −3 5 0
−2 2 −2 5
4 −2 13 −18
−6 5 −18 33
1 C C C A
+, -!
" 9 0 1 1 1/2 1/3 1/4 . . . B 1/2 1/3 1/4 1/5 . . . C B C B C 1/3 1/4 1/5 1/6 . . . C ∈ Rn,n , H := B B C B 1/4 1/5 1/6 1/7 C @ A
hik =
1 , i+k−1
#
: n +, - ( ;, # n = 3, 4, 5, . . . , 12" 3
" , 0 * ( $ κ(H ) # n , $+
< $ κ2 (H )
−0.24x1 −1.05x1
+1.76x2 +1.26x2 1.12x2
−0.69x3 −2.12x3 1.34x3
+0.76x4 +0.36x4 1.29x4
−0.30x5 +1.05x5 0.96x5
+0.66x6 +2.04x6
= 1.28 = 0.48 = 1.16 = −0.46 = −0.66 = −0.57
! " L R A #
0
Ax = b
1 B 1 B B B B B A=B B B B B @
1 2 1
1 1 3 1
1 4 1
1 4 1
1 3 1
1 2 1
C C C C C C C, C C C C 1 A 1
0 B B B B B B b=B B B B B @
1 0 0 0 0 0 0 0
1 C C C C C C C C C C C A
$ % RQ&' (&)&) $ !
f (x) x (xi , yi) g(x) ! " # $% % & g(xi ) g − y g = {g(xi )} y = {yi } % % g(x) − f (x) ' " ( ) * + ,g(xi ) = f (xi ) % g(xi ) = yi . , ' . % / $% ! 012 ' 3 4 ! " ' / , & " 5 % g(x) 6 5 ! , ! ! % 7
, ! " + (xi , yi), i = 0, 1, . . . , n, % 5 * 1 / n ( ' ) / 8 9 ! 01 : / ) " * xi yi % f (xi ) ' ! 01
yi
g(x) 0
0
−0.5
−1
f (xi )
g(x)
−0.5
x −1
0
1
−1
x −1
0
1
n + 1 x0 , x1 , . . . , xn y0 , y1 , . . . , yn n Pn (x) := a0 + a1 x + · · · + an xn ,
! Pn (xi ) = yi , i = 0, 1, . . . , n
"#
n+ 1 (xi , yi ) i = 0, 1, . . . , n xi = xj i = j Pn (x) !"#$ % & n " ' " $ % & '( %
) !
$ &# yi ( * +( f , &# xi ! , f (xi ) = yi ,
i = 0, 1, . . . , n,
( $ - (xi , yi ), i = 0, 1, . . . , n.
+ % # + ! $ + % # , ! % ( $ #
[a, b] ! !
"# !$
[a, b] f [a, b] (n + 1) f ∈ C n+1 [a, b] yi := f (xi ) , i = 0, 1, . . . , n Pn (xi , yi) %&'
ω(x) := (x − x0 )(x − x1 ) · · · (x − xn ) .
x˜ ∈ [a, b] ξ ∈ (a, b) f (˜ x) − Pn (˜ x) =
ω(˜ x)f (n+1) (ξ) . (n + 1)!
|f (˜ x) − Pn (˜ x)| ≤
!"
%('
|ω(˜ x)| max |f (n+1) (ξ)| . (n + 1)! ξ∈[a,b]
%)'
*
x˜ = xk + k ∈ {0, 1, . . . , n}
!
x ˜ = xi + i F (x) := f (x) − Pn (x) − K ω(x),
F ∈ C n+1 [a, b]
K F (˜ x) = 0 , ! ω(˜ x) = 0 ⇒ K =
x) f (˜ x) − Pn (˜ . ω(˜ x)
,
F (x) [a, b] (n + 2) , + ./
#$ - x0 , . . . , xn , x˜.
F (x)
0 1 - . - F (x) ··· ··· (n+1) (x) 1 - . F
2 - ξ F (n+1) / 0 = F (n+1) (ξ)
=
f (n+1) (ξ) −
0
P (n+1) (x)
⇒
K=
−K (n + 1)!
ω (n+1) (x)
f (n+1) (ξ) (n + 1)!
⇒ f (˜ x) − Pn (˜ x) = ω(˜ x)
f (n+1) (ξ) (n + 1)!
[a, b] ω ω
! "# $ % # &
' ( # $ i a+b b−a + cos π , i = 0, 1, . . . , n. xi = )*+, 2 2 n %- ./0'1/ 2 *34 .' /0'1 ! [x0 , xn ] $ & ω 2 *5 ω(x) 0.02
x −1
−0.5
0.5
1
−0.02
ω !" # ! !$ n%&
6 & ( • " 1/ *4 7 8 2 1/ 7'8 • 2 ' 8 8/ 9 9 : • 9 2 ' 8 7'8 ;" 2
P n + 1 n (x − xj ) Li (x) := (x i − xj ) j=0
j = i
=
(x − x0 ) · · · (x − xi−1 )(x − xi+1 ) · · · (x − xn ) (xi − x0 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xn )
! Pn (x) :=
n
yi Li (x).
i=0
" #
$% & # ! 1,
i = k, Li (xk ) = δik = 0,
i = k.
'(
Pn (x) ) ) * +, Qn (x) - . n Pn (xk ) = Qn (xk ) = yk , k = 0, 1, . . . , n,
''
, ) / + D(x) := Pn (x) − Qn (x) . - * n ) 0 n + 1 , - 1)
x0 , x1 , . . . , xn 1 2) + 3 ) D(x) = 0 ) Pn (x) = Qn (x)
+) 4 -
) )! Pn (x) := c0
+ c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + · · · + cn (x − x0 )(x − x1 ) · · · (x − xn−1 ).
'$
5 6+ ci ' 7)-
) )8+ - % , 9#+
) 9#+, + , ! Pn (x0 ) = c0
=⇒
c0 = y 0 y1 − y0 Pn (x1 ) = c0 + c1 (x1 − x0 ) =⇒ c1 = x1 − x0 ···
: 2 # ) 8) - 3);.) , : # - / + - - : #
8) - ! ( - / +! [yk ] := yk ,
k = 0, 1, . . . , n.
k = 0, 1, . . . , n − 1 [yk , yk+1 ] :=
yk+1 − yk [yk+1 ] − [yk ] = . xk+1 − xk xk+1 − xk
j [yk , yk+1 , . . . , yk+j ] := j = 2, 3, . . . , n,
[yk+1 , . . . , yk+j ] − [yk , . . . , yk+j−1 ] , xk+j − xk k = 0, 1, . . . , n − j.
! " # $ ∗ % $ ! &
Pk,k+1,...,k+j ! ! " j ' ! % (j + 1) ( xk , xk+1 , . . . , xk+j $ ) !
* +, ∗ Pk,k+1,...,k+j (xk+i ) = yk+i , i = 0, 1, . . . , j,
-
% . % Pk∗ (xk ) = yk = [yk ].
/
1 ≤ j ≤ n ∗ Pk,k+1,...,k+j (x) =
∗ ∗ (x) − (x − xk+j )Pk,...,k+j−1 (x) (x − xk )Pk+1,...,k+j xk+j − xk
∗ ∗ ! " Pk+1,...,k+j (x) % Pk,...,k+j−1 (x) 01 ! (j − 1) 2 % ) ! ( ( yk , . . . , yk+j ! ( xk , . . . , xk+j & ! ! 3 " !
∗ Pk,k+1,...,k+j (xk ) = yk
∗ % Pk,k+1,...,k+j (xk+j ) = yk+j ,
% i = 1, 2, . . . , j − 1 ∗ Pk,k+1,...,k+j (xk+i ) =
(xk+i − xk )yk+i − (xk+i − xk+j )yk+i = yk+i . xk+j − xk
4! (! ! ( ! % $ ! ∗ " Pk,k+1,...,k+j (x) ! & %
$! 5 (! ) ! [y0 , y1 , . . . , yj ] 67 cj 8 ) ! ! cj 01 97
∗ ! " P0,1,...,j (x) % (j + 1) ( % 9 (xi , yi )) i = 0, 1, . . . , j
n = 3 x0
y 0 = c0
x1
y1
[y0 , y1 ] = c1 [y0 , y1 , y2 ] = c2 [y1 , y2 ] x2
y2
x3
y3
[y0 , y1 , y2 , y3 ] = c3 [y1 , y2 , y3 ]
!"#$%
[y2 , y3 ]
& ' cj ( )# "#$ # & ' * * ' + , + # - ' ./ - !"#$0% - + Pn (x)
= c0 + c1 (x − x0 ) + · · · + cn (x − x0 )(x − x1 ) · · · (x − xn−1 ) = c0 + (x − x0 ) {c1 + (x − x1 ) [c2 + (x − x2 ) (
!"#$1%
· · · cn−1 + (x − xn−1 )cn )]} .
& ( ./ # & 2 ( )# "#$ #
$# - k = 0, 1, . . . , n ck := yk - k = 1, 2, . . . , n i = n, n − 1, . . . , k ci − ci−1 ci := xi − xi−k 0# 2 ' ./ p := cn - k = n − 1, n − 2, . . . , 0 p := ck + (x − xk )p - , p p = Pn (x)#
p := ln(1.57) ! ! "
# $ % x
1.4
1.5
1.6
1.7
ln(x)
0.3364722366
0.4054651081
0.4700036292
0.5306282511
1.4
0.3364722366 0.689928715
1.5
−0.22271752
0.4054651081 0.645385211
1.6
0.4700036292
1.7
0.5306282511
0.606246219
−0.19569496
0.0900752
! " ! #
$ %&'( )# & * ! + $ " )+ ! P1 (x) = 0.4054651081 + 0.645385211(x − 1.5).
, ,) ) ) -
$ "
! P2 (x)
=
0.3364722366 + 0.689928715(x − 1.4) − 0.22271752(x − 1.4)(x − 1.5)
=
0.3364722366 + (x − 1.4)[0.689928715 − (x − 1.5)0.22271752].
. +)! / ! ) $ " 0
P3 (x)
=
0.3364722366 + 0.689928715(x − 1.4) − 0.22271752(x − 1.4)(x − 1.5) +0.0900752(x − 1.4)(x − 1.5)(x − 1.6)
=
0.3364722366 + (x − 1.4)[0.689928715 +(x − 1.5){−0.22271752 + 0.0900752(x − 1.6)}]
=
P2 (x) + 0.0900752(x − 1.4)(x − 1.5)(x − 1.6).
1 ! 2 # 3! 4)
) +)! $ " + 0
+ & ) 5 &%67 "& . 8! 0 ) $ " 9) & : 5 4 ! ) 7 ln(1.57) = 0.4510756194& * ) P1 (1.57) = 0.4506420729 , P2 (1.57) = 0.4511097797 , P3 (1.57) = 0.4510776229 ,
4.3 · 10−4 # −3.4 · 10−5 # −2.0 · 10−6 &
! c˜j j! hj " #$ $ % $ & '("
) * + $ " , + $ -$ $$ " $ % . $$
xk
yk := f (xk ) f (xk + h) − f (xk ) f (xk + h) − f (xk ) = f (xk ). = h→0 (xk + h) − xk h m
xk 1 f (m−1) (xk ). [yk , yk , . . . , yk ] := (m − 1)! ! ! " # [yk , yk ] = lim
n + 1 $ $ x0 , x1 , . . . , xn % ! y0 , y1 , . . . , yn ! ! y0 , y1 , . . . , yn & ' P2n+1 $ () 2n + 1%
P2n+1 (xi ) = (xi ) = P2n+1
yi , i = 0, 1, . . . , n, yi , i = 0, 1, . . . , n.
* +)! ! ! % , - * n = 1 # x0 x0 x1 x1
y 0 = c0 y0 y1 y1
[y0 , y0 ] := y0 = c1 [y0 , y1 ] [y1 , y1 ] := y1
[y0 , y0 , y1 ] = c2 [y0 , y1 , y1 ]
[y0 , y0 , y1 , y1 ] = c3
* . ' / 0! 1# P3 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )2 + c3 (x − x0 )2 (x − x1 )
+
c0 + c1 (x − x0 ) + c2 (x − x0 )2 + c3 (x − x0 )2 (x − x1 ) c4 (x − x0 )2 (x − x1 )2 + · · ·
+
c2n+1 (x − x0 )2 (x − x1 )2 · · · (x − xn−1 )2 (x − xn ).
P2n+1 (x) =
f (x)
f (x)
=
x sin(5x)
=
x (sin(5x) + 5 cos(5x))
[0, 1]
!"# n + 1 $ xi " n = 1 % & ! ' & ! 0 0 1 1
0 = c0 0 −2.6066 −2.6066
5 = c1 −2.6066 1.2487
−7.6066 = c2 3.8554
11.4620 = c3
( % ) *% + [0, 1]
PH (x) = 5 x − 7.6066 x2 + 11.4620 x2 (x − 1).
f
1.5
f (x) x 1
0.5
−1.5
PH (x)
PN (x)
−3
· −
! f PN (x)
" # $%& ' # ! ( (% n + 1 $%& 2n + 2 $%& ) *
n %
[0, 1] # n+1
+ . 2
,//00 ///+. /////.
2n + 2
. 1 ,/
/./ // ///,/////..
) 3 & ! !" ) (
(xi , yi = f (xi )), i = 0, 1, . . . , n f x ¯ f (¯ x) = y¯ y¯ # $
yi
! "
f (x)
$ % !
&$ ' %$ () $ ) '
x = Q(y)
$ $ * + & $,
yi
xi
$
- $ $ &
y¯ = 0
$
* 0 $
' $ ./.
2
y
1
Q(y)
P (x)
−1
x 1
2
3
−1
n = 2
xi −1 1 3
yi −1 1 2
1 1/2
−1/8
! "#$ 1 y = P2 (x) = −1 + (x + 1) − (x + 1)(x − 1). 8 yi −1 1 2
xi −1 1 3
1 2
1/3
1 (y + 1)(y − 1). 3 % & ' $ #$ ' ¯ = Q2 (¯ y) = y ( y¯ = 0 ) ' ) $* ( x −1/3 ) + x = Q2 (y) = −1 + (y + 1) +
! " # $ #
% &'()
a = x0
a
x1
x2
x3 = b
ξ
x
g(x)
x
g (x)
x
g (x)
x
g (3) (x)
b
n x i ! " # 1 , λi := (xi − x0 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xn ) n dn Pn (x) = yi n!λi ≈ f (n) (x) dxn i=0 $ %&&' n %( f (n) (x) )
f (x) [a, b] a = min (xi ), b = max(xi ) n i i
ξ ∈ (a, b)
f (n) (ξ) =
n
yi n!λi .
i=0
* ( + , g(x) := f (x) − Pn (x)- Pn (x) . &
& # / xi - i = 0, 1, . . . , n, / yi = f (xi ) ( g(x) . &
0 (n + 1) x0 , x1 , . . . , xn * 0 g(x) n / 1 2 - 0 )' / ξ . , $ . 1 - / 3 (n) g (n) (ξ) = f (n) (ξ) − Pn (ξ) = 0 ( 4& . %(( 5 / , , + n = 3 , 3 %&&' n %( ( ( + , % 0 36
/ xi = x0 + ih- i = 0, 1, . . . , n, 1 1 λi = 7 (xi − x0 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xn ) =
# $ (−1)n−i n 1 = , (−1)n−i hn [i(i − 1) · · · 1][1 · 2 · · · (n − i)] hn n! i
' # $ 1 n y1 + (−1)n−2 f (n) (x) ≈ n (−1)n y0 + (−1)n−1 h 1 # $ ( # $ n n y2 + . . . − yn−1 + yn . 2 n−1
n f (n) (x) hn ! " # $ % yi & '#( ) % & % ! # % n (n+1) $ % yi * n = 1, 2 3 * + f (x) ≈
y 1 − y0 h
f (x) ≈
y2 − 2y1 + y0 h2
f (3) (x) ≈
y3 − 3y2 + 3y1 − y0 h3
+ , + ,
-
+ ,
$ ξ & % n + , n n + *# f (x) # &
./ 0
# xM = (x0 +xn )/2 1 * ! 2 *# % + , - 3 0
1 ! p *# # 4 5 1 6 Pn (x) n > p % 7 p
(p) Pn (x) # & $ x 2 % 8 1 f (x) 4 , 1 6 % 0 9:; < y0 (x − x1 )(x − x2 ) − 2y1 (x − x0 )(x − x2 ) + y2 (x − x0 )(x − x1 ) , 2h2 y0 (2x − x1 − x2 ) − 2y1 (2x − x0 − x2 ) + y2 (2x − x0 − x1 ) P2 (x) = . 2h2 * $ x0 & x1 x2 P2 (x)
=
f (x0 ) ≈ f (x1 ) ≈ f (x2 ) ≈
1 [−3y0 + 4y1 − y2 ] 2h 1 [−y0 + y2 ] 2h 1 [y0 − 4y1 + 3y2 ] 2h
= 9 ;
# 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 • ! $ ! ! ! *! ! : $ ! ! ,
/ ;<
(7 "! ! 2 k = 3 ! p = 2
f 1.5
1
0.5
x 0 0
1
2
3
4
5
6
−0.5
!" # $% "& !'& #" (% # )! #%( * + $,! ' -. *( / % 0!! # 1 ! 2+ 2%& !
! "
3
! *( (
n + 1 + + % ,+ [a, b] a = x0 < x1 < · · · < xn = b
% y0 , y1 , . . . , yn
$445'
s s s(xi ) = yi i = 0, 1, . . . , n. s [a, b] !" # (xi , xi+1 ) i = 0, 1, . . . , n − 1 s !" $ % & '( )"* +" xi '( * s ) 1 b 2 J[s] := s (x) dx. , 2 a - '( . / 0 + " 1 '( '( 2 )" "2 "
*b '( / a |s (x)| dx
s
3 '(4 2* 56 78 '( 1 '( " + * 2 s 94 - 0 0 6& ( : * & " $ +" ( $ ('( * * . + 2 2&+ '(; ( $'( 77 7
< ;'( * *
s % & = - 1 '( 0 " '( 2 s '( - * s " = + s = + s1 = - s1
J[s] ≤ J[s1 ].
s1 *;( * " s1 (x) = s(x) + ε h(x).
>
- ε ? * s1 2 = h 0'( )'( h(xi ) = 0,
i = 0, 1, . . . , n.
:
@ h 2 (A * s1 = + ) 1 b 2 J(ε) := J[s1 ] = (s (x) + εh (x)) dx. : 2 a
J(ε) ε ε = 0 ! " J (0) =
dJ =0 dε ε=0
# $ % & ' h.
()
$
" J (0) =
)
b
s (x)h (x) dx.
(
a
* + ' $ , " / ) )
xi+1
xi xi+1
s (x)h (x) dx
s(3) (x)h (x) dx
xi+1 ) xi+1 = s (x)h (x) − s(3) (x)h (x) dx, xi xi xi+1 ) xi+1 = s(3) (x)h(x) − s(4) (x)h(x) dx. xi
xi
# -.
xi
! #$" h(xi ) = 0 0$ - " 1' J (0)
= −s (x0 +)h (x0 ) + (s (x1 −) − s (x1 +)) h (x1 ) + (s (x2 −) − s (x2 +)) h (x2 ) + · · · + s (xn −)h (xn ) ) b + s(4) (x)h(x) dx.
((
a
*1 s (xi +) 1$ s (xi −) 2 $ / s " xi %
x / 1$ / '
* h 11 $ % & ' '" J (0) = 0 $ ! " s(4) (x) = 0 x = x0 , x1 , . . . , xn .
(3
% " % $! s(4) (ξ) > 0 ' - /" '4 $ % h 5 h(ξ) > 0
' 61 ' ξ *
, - / ,/ + 7 (( % J (0) > 0 , $ () 8 s (x0 +) = s (xi −) =
s (xn −) = 0 s (xi +), i = 1, 2, . . . , n − 1;
(9 (:
s ½ s (xk −) − s (xk +) = 0 k h h (xi ) = 0 ! xk J (0) = 0 " #$%&' ( #$%)' s * + [xi , xi+1 ] , . si (x) ( #' #' #$%/' , ( 0
1 si (xi ) si (xi ) si (xi )
⎫ = si−1 (xi ), ⎪ ⎪ ⎬ i = 1, 2, . . . , n − 1. = si−1 (xi ), ⎪ ⎪ ⎭ = si−1 (xi ),
#$%2'
(! #$%/' s0 (x0 ) = sn−1 (xn ) = 0.
#$%3'
4 0 s 5 " s 6 , {s0 , s1 , . . . , sn−1 } 7 4 , . 8 9 " + : si ; " #'1 si (xi ) = yi ,
si (xi+1 ) = yi+1 .
#$)'
< .:! ci := s (xi )
#$) '
0 < si (xi ) = ci ,
si (xi+1 ) = ci+1 .
#$)&'
* t :=
x − xi , hi
hi := xi+1 − xi
#$)$'
+ [xi , xi+1 ] = [0, 1] si qi (t) = si (x) = si (xi + hi t).
#$)%'
½
qi qi (0) = yi , qi (0) = hi ci ,
qi (1) = yi+1 , qi (1)
= hi ci+1 .
! " #$ % & ! # ' ( ! )* qi (t) =
(1 − t)2 yi + t2 yi+1 + t(1 − t) {(1 − t)(2yi + hi ci ) + t(2yi+1 − hi ci+1 }
+
$ % , - s s $
qi (0) = 6(yi+1 − yi ) − 2hi (2ci + ci+1 ), qi (1)
. /
= −6(yi+1 − yi ) + 2hi (ci + 2ci+1 ).
0 si (x) = qi (t)(dt/dx)2 = qi (t)h−2 &1 2
i s ( % &1 ,
, 1
(2c0 + c1 )/h0
=
3(y1 − y0 )/h20 ,
3
(cn−1 + 2cn )/hn−1 = 3(yn − &1 i = 1, . . . , n − 1 : (ci−1 + 2ci )/hi−1 + (2ci + ci+1 )/hi = 3(yi − yi−1 )/h2i−1 + 3(yi+1 − yi )/h2i . yn−1 )/h2n−1 ,
, n + 1 4 &1 n + 1 5 #
c0 , c1 , . . . , cn , 67 8 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
2 h0 1 h0
0
⎞
1 h0 2 2 + h0 h1 1 h1
0 1 h1 2 2 + h1 h2
1 h2
1 hn−2
2 2 + hn−2 hn−1 1 hn−1
1 hn−1 2 hn−1
⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
- 6 #, 4 # + 9! % : 4 3
s ! [xi , xi+1 ] " #$ #$ %& si (x) '( s $)
#$ * + +, $ - #$ ." /'' ' / #$ #$ 0" 1 0 " #$ $(2 0 3 4#$ /'3 s (x0 ) = 0 s (xn ) = 0, 5 ( /'3 s (x0 ) = y0 , s (xn ) = yn , % #$ /'3 s (x0 ) = s (xn ) s (x0 ) = s (xn ). 0 (0#$ - " " 1 ' .''6 1/' "($ " " (#$ . #$ #$( " / #$ & #$ * #$ 7 #$ $ #$ /'. " ' .''6
$ #$ 0 /' $ . $ #$ 1 " '6 #$ $ #$#$ 8 " $ 1 9 1/' 1 ' " /0 $ #$ 1 /' : #$#$ #$ ; " < $ #$ #"
x0 < x1 < x2 < x3
! • " [x0 , x1 ]! [x1 , x2 ] [x2 , x3 ] # $ ! • % & ' ! •
() ** + 1
Bi (x) B0
0 x0
B2
B1
x1
x2
B3
x x3
** + , -. /
! "! #$ "! % & % " $ % ' % (
t0 := t1 := x0 , t2 := x1 , t3 := x2 , t4 := t5 := x3 .
*+ , - . /
( (t − x) t ≥ x Fx (t) := t < x 0
)
)0
Fx (t) % x t ( 1 ' ti % fi := Fx (ti ) "! 2 3 , * . 1 % B0 4
)5
B0 (x) := (t2 − t0 )[f0 , f1 , f2 ] .
2 " 6 3 x t!1 fi $ x Bi # % 1 7 ! 2 !( * .0 * % B0 7 ! 4
*
ti x0
Fx (ti ) 0
x0
0
x1
x1 − x
0 x1 − x x1 − x0
8 < x1 − x x1 − x0 B0 (x) = : 0
x1 −x x1 −x0
x1 − x0
x ∈ [x0 , x1 ]
.
))
7 $ " B1 (x) := (t3 − t1 )[f1 , f2 , f3 ] ,
, - 7 ! *
8 x1 − x x − x0 > 1− = x ∈ [x0 , x1 ] > > x1 − x0 x1 − x0 > < x2 − x B1 (x) = x ∈ [x1 , x2 ] > > x 2 − x1 > > : 0
, % * 8
!
αi , i = 0, . . . , n, n αi Bi (xk ) = yk , k = 0, 1 . . . , n.
i=0
! Bi (xk ) =
1 0
i=k i = k
αi := yi .
! " # $ %"& '" "& ( )&" " " ! " %" # *( ' & + ' " %
, ( " & %" # -. '" " /
'" && '" -'" . '" 0 & $ ( ' & {xi } ' 1 " % & {ti } 2
{t0 , t1 , t2 , t3 , t4 , t5 , . . . , {x0 , x0 , x0 , x0 , x2 , x3 , . . . ,
tn , tn+1 , tn+2 , tn+3 , tn+4 } xn−2 , xn , xn , xn , xn } .
:=
*( 1 " % t0 , t1 , . . . , tn+4 . 3 ,
⎧ ⎨ 1 = 1 ⎩ 0
Bi,0 (x)
⎫ ti ≤ x < ti+1 ⎬ i = 0, 1, . . . , n + 3. x = ti+1 = xn ⎭
45 /
Bi,0 (x) ≡ 0 ti = ti+1 -
, "
3 , %" #2
Bi,k (x) =∗ =∗ "
x − ti ti+k+1 − x Bi,k−1 (x) + Bi+1,k−1 (x). ti+k − ti ti+k+1 − ti+1
46
7& & 8 "
" 1 " % & " 3 ,
%" #
B0,0 ↓ B0,1 ↓ B0,2 ↓ B0,3
B1,0 B2,0 . . . ↓ ... B1,1 ... ... ↓ ... ... B1,2 ... ... ↓ ... ... B1,3 ... ...
Bn,0 ↓ Bn,1 ↓ Bn,2 ↓ Bn,3
Bn+1,0 ↓ Bn+1,1 ↓ Bn+1,2
Bn+2,0 ↓ Bn+2,1
Bn+3,0 49
x ∈ [ti , ti+1 ] ti < ti+1 Bi,k (x) k = 0, 1, 2, 3 x ! " #! $
0 Bi,0 0
0 Bi−1,1 Bi,1 0
0 Bi−2,2 Bi−1,2 Bi,2 0
0 Bi−3,3 Bi−2,3 Bi−1,3 Bi,3 0
%&'()
* ! +" ,! ! ! *! * - ! . / Bi (x) := Bi,3 (x) ! $ +/"$ B0 (x) > 0 x ∈ [x0 , x2 ), B1 (x) > 0 x ∈ (x0 , x3 ), B2 (x) > 0 x ∈ (x0 , x4 ), B3 (x) > 0 x ∈ (x0 , x5 ), Bi (x) > 0 x ∈ (xi−2 , xi+2 ), i = 4, . . . , n − 4, Bn−3 (x) > 0 x ∈ (xn−5 , xn ), Bn−2 (x) > 0 x ∈ (xn−4 , xn ), Bn−1 (x) > 0 x ∈ (xn−3 , xn ), Bn (x) > 0 x ∈ (xn−2 , xn ]. #0 1" n 2 Bi (x) = 1 ∀x ∈ [x0 , xn ] &
%&' )
i=0
34 B ,!5 bik := Bk (xi ) %&'2) - / 6 7 !" 8 % ) * ,! ti / "! xi */ * 9 * # 1 " # : !" . # ! ; "! < 1 - /= *! * ! xi := x0 + ih, i = 0, 1, . . . , n.
B0
1/8
1
37/72
B1
1/9
B2 23/72
5/9
1/8
1/3
17/24
B3 1/24
1/6 × × × × x0
x1
1/6
2/3
1/6
×
×
×
×
x2
x3
x4
x5
B4 ×
x6
i = 4, 5, . . . , n − 4 1 Bi (x) = 3 · 6h ⎧ (x − xi−2 )3 , ⎪ ⎪ ⎪ h3 + 3h2 (x − x ) + 3h(x − x )2 − 3(x − x )3 , ⎪ ⎨ i−1 i−1 i−1 h3 + 3h2 (xi+1 − x) + 3h(xi+1 − x)2 − 3(xi+1 − x)3 , ⎪ ⎪ ⎪ − x)3 , (x ⎪ ⎩ i+2 0,
x ∈ [xi−2 , xi−1 ], x ∈ [xi−1 , xi ], x ∈ [xi , xi+1 ], x ∈ [xi+1 , xi+2 ],
! " × ! ! #$ %&! ' ' ' ( ) 4 &* {xi−2 , . . . , xi+2 } + yi = {0, 1/6, 2/3, 1/6, 0} .
! "# $ " ! $ % % % &$ '%% ($ $ %$ )
tj
tj
m (3 − m)
Bi
"$ * $ + % $ *$ , - . 1
f
x 0 0 × × × ×
1 ×
2 × ×
3 × × ×
5 ×
4 ×
" $ s(x) ' % ) s(x) =
n
αk Bk (x).
/--0
k=0
" , % n+1 n+1 1 $ '+ ( ! $ % 2 $ " 3 , $ $ 1 /, $
-4 0
Bα = y αk α y αk yi !" # n αk Bk (xi ) = yi , i = 0, 1, . . . , n. $% &'( k=0
) * ) + * ,-! . /, 0 1
- m -2 m > n + 1" 3 4!!5 )2" 4 % 6 * !
Bα = y " B 7 85
8 9 " ! 6" # n 2 m αk Bk (xi ) − yi → min $% &:( i=0
αi
k=0
20
P (x) 15
10
f (x)
5
0
10
20
30
40
50
60
20
30
40
50
60
10 8 6 4 2 0
f (x) s(x) 10
x
P (x)
s(x)
f (x) =
0.1 0.3 0.5 0.7 0.9 51.0 53.0 55.0 57.0 59.0 61.0 63.0
0.128820 0.364987 0.574768 0.760697 0.925141 18.501183 35.466596 56.773501 78.917289 94.778908 92.051716 51.276268
0.124346 0.355691 0.564967 0.753454 0.922429 7.141938 7.281021 7.417362 7.551075 7.682272 7.811066 7.937570
√ x
0.316227 0.547722 0.707106 0.836660 0.948683 7.141428 7.280109 7.416198 7.549834 7.681145 7.810249 7.937253
!" # √ f (x) = x
[0, 64]
$ x y
0 0
1 1
4 2
9 3
16 4
25 5
36 6
49 7
64 8
% & #& ' " (" ) "
* +
" # ,
(0, 1) √ " (49, 64)
!" # f (x) = x " - " & . // 0 !" # f " P P 1
# " x ≈ 50 "
" ' 1" /22 " f " " # s 1 " 1 3 1
s .
" &
(xk , yk , fk ) k = 1, 2, . . . , m.
S(x, y) :=
n l
cνμ sν (x)tμ (y) l n = m
ν=1 μ=1
S(xk , yk ) = fk , k = 1, 2, . . . , m.
sν tμ
(xk , yk , fk ) k = 1, 2, . . . , m.
S(x, y) :=
l n
cνμ sν (x)tμ (y) l n < m
ν=1 μ=1 m
(S(xk , yk ) − fk )2 → min . cνμ
k=1
! " #$ % &'() " '( *! +'('% '(,-
" . # "xi , i = 1, 2, . . . , n yj , j = 1, 2, . . . , l fij , i = 1, 2, . . . , n, j = 1, 2, . . . , l. n l S(x, y) := cνμ sν (x)tμ (y)
ν=1 μ=1
S(xi , yj )
=
fij , i = 1, 2, . . . , n, j = 1, 2, . . . , l.
% /'( " " 0 '( ! " . !!
1 " " ,'( R3 '( 2 0'" 2 3 '( 4# ' 5 2! , '( '( 6! 0%) " 7 % '( " . !! ,'( /'( ( " 6 f : Qk → R %% Qk = {(x, y)| − k ≤ x, y ≤ k} 8
6,% 2k.
⎧ ⎨ 1 + t −1 ≤ t < 0 B1 (t) := 1−t 0≤t<1 ⎩ 0 sonst
D11 (x, y) := B1 (x)B1 (y),
(x, y) ∈ R2 ,
−1 < x, y < 1 ! " # z = 0 $ % & '
( )
fij , S S(i, j) = fij , S
−k ≤ i, j ≤ k,
k ∈ N∗
−k ≤ i, j ≤ k.
S(x, y) =
k
k
fij D11 (x − i, y − j),
(x, y) ∈ R2 .
i=−k j=−k
% &
! *
n ν=0
aν ϕν (k) = fk ,
k = 0, . . . , n,
(fk )k=0,...,n ∈ Rn+1
m n
!
aνμ Dνμ (k, l) = fkl
ν=0 μ=0
! Dνμ (x, y) := ϕν (x)ϕμ (y)
k = 0, . . . , n l = 0, . . . , m
ν = 0, . . . , n μ = 0, . . . , m
(fkl ) ∈ R(n+1)(m+1)
m n
aνμ Dνμ (k, l) =
ν=0 μ=0
n # m ν=0
$ aνμ ϕμ (l) ϕν (k).
μ=0
τνl :=
m
! aνμ ϕμ (l),
μ=0
ν = 0, . . . , n l = 0, . . . , m,
n
! τνl ϕν (k) = fkl
ν=0
k = 0, . . . , n . l = 0, . . . , m
m + 1 τνl
n + 1 m
! aνμ ϕμ (l) = τνl
μ=0
l = 0, . . . , m, ν = 0, . . . , n,
!
" # $ % $
# # & " '
k = 10
[−10, 10] × [−10, 10]
x f (x, y) = exp 10
!
! |y| . 10
p exp
x f (x, y) = exp 10
!
p ! |y| exp 10
sν (x)
:=
tμ (y) :=
Bν (x),
ν = 1, 2, . . . , n,
Bμ (y), μ = 1, 2, . . . , l.
Bν (x) Bμ (y) !" # "" $ {xi } {yj } % ¾ &$$ $ ' () ' *! $ ) " !" $ +× + ,
$ - . $ ) " )
ˆνμ (x, y) := Bν (x)Bμ (y). B
-
/ $ 0 Rη , 1)"* )$ ()$ 23 45 ˆνμ (x, y) = B
3 3
aij xi y j , "" (x, y) ∈ Rη .
6
i=0 j=0
7 8)9 aij ) () !" / (ν, μ) $ 0 Rη # $ ") " / : ) 0
$" ; #
""
8 ) ! (
! $ $ ) " :"" <3 / !)") !)"$
$ 0 + " ¾ B B B˜
l n
cνμ Bν (xi )Bμ (yj ) = fij , i = 1, 2, . . . , n, j = 1, 2, . . . , l.
ν=1 μ=1
n × l ! " # $%$#% & '( ! # #) # )" * + !#, "$ )" QR%& -) . " +, # # '( # /" -))% + # ! 0 1 (xi , yi , fi ), i = 1, 2, . . . , m.
! # " l n
cνμ Bν (xi )Bμ (yi ) = fi , i = 1, 2, . . . , m.
0
ν=1 μ=1
2 ! # # $%) / # /" {xi } # {yi } % , # , # # /" , 3 -) # * # -) 3 # # /" # # * # /"! # % 0 ! # ) # ! &% # ) +!# 0 +/ m = n l 4 # # 3 # $# " /, ( # 5 # # 6 # # +/ m ≤ n l 7 )% ( # +/ m > n l .)) 8(
F (x, y) !
" #$ % &'% ( ) %* + % , &'% () % ,!
% %* % -. / $ * 0 123 , %
F (x, y)
S(x, y)
y ! "# F (x, y) := −2
5 8 1 a12 )2 a + 65 a2 + 12 a12 (a1 + a2 + 168 5 1 + 2 5 5 25 5 5 25 (1 + 8 a1 + 6 a2 + 2352 a12 )2 1 + 8 a1 + 6 a2 + 2352 a12
$$"
128 54 182 8 6 14 y − x), a2 := exp( y − x), a12 := exp( y− x). 125 5 125 5 125 5 % &
'((& [−8, 7] × [−8, 7] & ( ) &
* + &
* ) ,, - & '((& % & *. * x y ' ( ( ( )( ' & /, 0 ,* ,* , " % , 20 × 20 = 400 & % 1.( * * ) 31 × 31 2 & , ( (" % 3
* 45 & 6(& ) % * ( & a1 := exp(
n + 1 x(i) ∈ Rm (i)
(i)
x(i) = (x1 , x2 , . . . , x(i) m ), i = 0, 1, . . . , n.
! "# "! t ∈ R $ %& & $ "
" m ""!'
x1 (t), x2 (t), . . . , xm (t), t ∈ [0, 1],
(
% ) !* " ti *$ '+ , (i)
xk (ti ) = xk , i = 0, 1, . . . , n, k = 1, 2, . . . , m.
n + 1 x(i) ti t0
:=
ti
:=
0
+ ,m , (i) (i−1) 2 ti−1 + - (xk − xk ) , i = 1, . . . , n.
k=1
ti ! " [0, 1] ti :=
ti , i = 1, . . . , n. tn
# m $% % & $ & (i) ti ' $ & & k ( $% xk (t) ) xk m * & +" R (x1 (t), x2 (t), . . . , xm (t)),
t ∈ [0, 1].
,
! "# #$ r(t) = c t (1 +
bct sin(a t) ). d
% &'(
) (r, t) * + , " t ! ϕ -) * . / $ d = 500 $ c=2$ b = 0.2 $ a = 5.03 $
0# "/ 1) 2 1) 23 #
* ) x(t) y(t)
= =
r cos(t) , r sin(t) .
% &4(
5 6 # ) '7 8774 * " ) )) 84 2 ) , "
'7 * #+ ) 8774 * ) , " * 9# #+
0) -# + ) 6 + .2 : * . 2 /$ ;+ <#, " = / % ) '(+ ;= /
! !! "
n # $ n (1 − t)n−i ti . 1 = ((1 − t) + t)n = i i=0
n t # $ n (1 − t)n−i ti , Bin (t) := i
i = 0, 1, . . . , n,
[0, 1] !
" # $ % & ' ( ) * +,,- & #& .
i n [a, b] u−a u ∈ [a, b] → t ∈ [0, 1] : t = b−a i = 0, 1, . . . , n $ # # $ 1 u−a n = (b − u)n−i (u − a)i . Bin (u; a, b) := Bin !"#$$% n b−a (b − a) i & ' ' ( ' ) * + [0, 1] # , -* ' ' ' ' . /0 1 $2# y 1
B06 (t)
0.5
B66 (t)
B16 (t)
B36 (t)
B56 (t)
t
0 0
1
0.5
n ∈ N∗ ,
0 ≤ i ≤ n Bin (t)
t = 0 i Bin . t = 1 (n − i) Bin . Bin (t) = Bn−i,n (1 − t)
0 ≤ Bin (t) ≤ 1 ∀t ∈ [0, 1], Bin (t) > 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: ' ;' ! ! (
' ; ' ! ! ;' ! < 8 " & H ! ( &' =; 9; (·, ·) > · * ! 7 >' $ (f, f ) = f 2 ∀f ∈ H ! < H ;? {ϕ0 , ϕ1 , . . . , ϕn }! f ∈ H !
g f g ! " # $% αj & n g(x) := g(x; α0 , α1 , . . . , αn ) := αj ϕj (x). '( ()* j=0
+ , - # $% αj . '( (/*
F (α0 , α1 , . . . , αn ) := f − g2 → min . αj
ϕj , j = 0, . . . , n, ! ⎛
(ϕ0 , ϕ0 )
⎜ ⎜ (ϕ1 , ϕ0 ) ⎜ ⎜ ⎝
(ϕ0 , ϕ1 )
(ϕn , ϕ0 )
···
···
···
⎞⎛
⎞ ⎛ α0 (f, ϕ0 ) ⎟ ⎜ α1 ⎟ ⎜ (f, ϕ1 ) ⎟ ⎟⎜ ⎟ ⎜ ⎜ ⎟=⎜ ⎟ ⎝ ⎠ ⎠ ⎝ αn (f, ϕn ) (ϕn , ϕn ) (ϕ0 , ϕn )
⎞
⎟ ⎟ ⎟. ⎠
'( (0*
" # 1 $ % % &' ( ) * + ! ,#
1 ! 2 . F '( (/* αj ! 3 F (α0 , . . . , αn )
= ||f − g||22 = (f − g, f − g) n n αj ϕj , f − αj ϕj ) = (f − j=0
= (f, f ) − 2
j=0
αj (f, ϕj ) +
j
j
αj αk (ϕj , ϕk ).
k
! - 2 n 1 ∂F = −(f, ϕk ) + αj (ϕj , ϕk ) = 0, 2 ∂αk j=0
k = 0, 1, . . . , n.
2 3% . %! / 0 ∂2F = (ϕj , ϕk ) ∂αj ∂αk
4
% ! %" %,
{ϕj }nj=0
(ϕj , ϕk ) = 0 ! .
ϕj αj α ϕ j j j = 0 H αk = 0
!
(αj ϕj , ϕk ) =
j
" "#
αj (ϕj , ϕk ) = 0, k = 0, . . . , n
j
/ 0 $% &' ( (ϕj , ϕk ) = 0
) * . $ ! " "# $% &' {αj }+ j αj (ϕj , ϕk ) = 0 , ( + j
αj (ϕj , ϕk ) αk = ( αj ϕj , αk ϕk ) = αk ϕk 2 = 0, j
k
(
. k
k
k
αk ϕk = 0 H {ϕj }nj=0
- . * /*! {ϕj } ( 0 1 (ϕj , ϕk ) &' , 0 1 2
3% 4 5 6 3 &' , 0 0 3 " "7 ' 8 91 0 * &' -331$ ( :* 9 - "7