›
›

Bài giảng Giải tích số

pdf 74 trang ngocly 140 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải tích số", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_giai_tich_so.pdf

Nội dung text: Bài giảng Giải tích số

  1. TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA TOÁN - TIN HỌC Y Z GIẢI TÍCH SỐ (Baøi giaûng toùm taét) NGƯỜI BIÊN SOẠN LÊ MINH LƯU Y Ñaø Laït 2009 Z
  2. Môc lôc 1 Ch−¬ng 1 Lý thuyÕt sai sè 3 1.1 C¸c lo¹i sai sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.2 Quy t¾c thu gän sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Ch÷ sè ch¾c, kh«ng ch¾c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 1.4 Hai bµi to¸n vÒ sai sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Sai sè c¸c phÐp to¸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 Ch−¬ng 2 XÊp xØ tèt nhÊt 8 2.1 XÊp xØ tèt nhÊt trong kh«ng gian ®Þnh chuÈn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 XÊp xØ tèt nhÊt trong kh«ng gian c¸c hµm liªn tôc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 XÊp xØ tèt nhÊt trong kh«ng gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Ch−¬ng 3 XÊp xØ hµm b»ng ®a thøc néi suy 19 3.1 Bµi to¸n néi suy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 3.2 Gi¶i hÖ ®¹i sè tuyÕn tÝnh ®Ó x¸c ®Þnh ®a thøc néi suy . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 3.3 Ph−¬ng ph¸p néi suy Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Tr−êng hîp c¸c mèc néi suy c¸ch ®Òu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 3.5 Sai sè cña p−¬ng ph¸p néi suy Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6 Chän mèc néi suy tèi −u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 Ch−¬ng 4 TÝnh gÇn ®óng ®¹o hµm vµ tÝch ph©n 31 4.1 Dïng néi suy Lagrange tÝnh gÇn ®óng ®¹o hµm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 TÝnh gÇn ®óng tÝch ph©n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Ch−¬ng 5 Gi¶i ph−¬ng tr×nh phi tuyÕn 37 5.1 Ph−¬ng ph¸p ®å thÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Ph−¬ng ph¸p chia ®«i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.3 Ph−¬ng ph¸p lÆp ®¬n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 5.4 Ph−¬ng ph¸p d©y cung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 5.5 Ph−¬ng ph¸p tiÕp tuyÕn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.6 Gi¶i ®a thøc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.7 Gi¶i hÖ hai ph−¬ng tr×nh phi tuyÕn b»ng ph−¬ng ph¸p lÆp ®¬n . . . . . . . . . . . . . . . . . . . .46 Ch−¬ng 6 Gi¶i hÖ ph−¬ng tr×nh ®¹i sè tuyÕn tÝnh 47 6.1 Mét vµi kh¸i niÖm cÇn thiÕt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
  3. Gi¶i tÝch sè 2 6.2 Ph−¬ng ph¸p Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.3 Ph−¬ng ph¸p c¨n sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51 6.4 Ph−¬ng ph¸p lÆp ®¬n gi¶i hÖ ®¹i sè tuyÕn tÝnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.5 Ph−¬ng ph¸p Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 6.6 Ph−¬ng ph¸p Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.7 Ph−¬ng ph¸p Gauss‐Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Ch−¬ng 7 Gi¶i gÇn ®óng ph−¬ng tr×nh vi ph©n 59 7.1 Ph−¬ng ph¸p xÊp xØ liªn tiÕp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59 7.2 Ph−¬ng ph¸p chuçi nguyªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3 Ph−¬ng ph¸p Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 7.4 Ph−¬ng ph¸p Euler c¶i tiÕn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7.5 Ph−¬ng ph¸p Runge‐Kutta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Tµi liÖu tham kh¶o 68
  4. Gi¶i tÝch sè 3 Ch−¬ng 1 Lý ThuyÕt Sai Sè 1.1 C¸c lo¹i sai sè Trªn thùc tÕ khi ®o mét ®¹i l−îng hoÆc x¸c ®Þnh mét ®¹i l−îng mµ ta ký hiÖu lµ a∗, th«ng th−êng kh«ng x¸c ®Þnh ®−îc gi¸ trÞ ®óng mµ chØ biÕt ®−îc gi¸ trÞ gÇn ®óng a. VËy ta ®∙ gÆp ph¶i sai sè. Cã nhiÒu lo¹i sai sè: 1. Sai sè thùc sù: §¹i l−îng 4 := |a − a∗| gäi lµ sai sè thùc sù cña a. 2. Sai sè tuyÖt ®èi: NÕu biÕt 4a ≥ 0 sao cho ∗ a − 4a ≤ a ≤ a + 4a th× 4a gäi lµ sai sè tuyÖt ®èi cña a. 3. Sai sè t−¬ng ®èi: §¹i l−îng 4 δ := a a |a| gäi lµ sai sè t−¬ng ®èi cña a. 1.2 Qui t¾c thu gän sè Gi¶ sö ta cã sè gÇn ®óng a ®−îc viÕt d−íi d¹ng thËp ph©n p j p−s a = ±(βp10 + + βj10 + + βp−s10 ) trong ®ã βj ∈ {0, 1, 2, , 9}, βp > 0. Ta muèn thu gän sè a ®Õn hµng thø j. Gäi sè a lµ sè thu gän ®Õn hµng thø j cña sè a vµ phÇn vøt bá lµ µ. §Æt: p j+1 j a = βp10 + + βj+110 + βj10 . j j j Trong ®ã: βj b»ng βj + 1 nÕu 0, 5 × 10 < µ < 10 vµ b»ng βj nÕu 0 ≤ µ < 0, 5 × 10 . j Tr−êng hîp µ = 0.5 × 10 th× βj = βj nÕu βj ch½n vµ βj = βj + 1 nÕu βj lÎ. Nh− vËy sai sè thu gän lµ ®¹i l−îng Γa ≥ 0 tháa |a − a| ≤ Γa.
  5. Gi¶i tÝch sè 4 Do p j a = ±(βp10 + + βj10 + µ), p j j a = ±(βp10 + + βj10 + βj10 ), ta cã j j |a − a| = |(βj − βj) × 10 + µ| < 0.5 × 10 . VÝ dô: Sè π ' 3, 1415 ' 3, 142 ' 3, 14. Chó ý 1. Sai sè tuyÖt ®èi kh«ng ®Æc tr−ng cho ®é chÝnh x¸c cña phÐp ®o mµ chØ cho phÐp ta h×nh dung ®−îc ®é gÇn nhau gi÷a gi¸ trÞ ®óng vµ gi¸ trÞ gÇn ®óng. 2. Sai sè tuyÖt ®èi cïng thø nguyªn víi ®¹i l−îng ®o. 3. Sai sè t−¬ng ®èi ®Æc tr−ng cho ®é chÝnh x¸c cña phÐp ®o vµ kh«ng cã thø nguyªn. 4. Sau khi thu gän sè th× sai sè tuyÖt ®èi t¨ng lªn. Gäi a∗ lµ gi¸ trÞ ®óng, a lµ gi¸ trÞ gÇn ®óng vµ gäi a lµ sè sau khi thu gän cña a th× ∗ ∗ |a − a| ≤ |a − a| + |a − a| ≤ 4a + Γa. 1.3 Ch÷ sè ch¾c vµ kh«ng ch¾c Gi¶ sö cã sè gÇn ®óng a viÕt ë d¹ng p j p−s a = ±(βp10 + + βj10 + + βp−s10 ). i Víi sai sè tuyÖt ®èi cña a lµ 4a. Cho sè 0 < ω ≤ 1. NÕu 4a ≤ ω × 10 th× ch÷ sè βi gäi lµ ch÷ sè ch¾c, ng−îc l¹i ch÷ sè βi gäi lµ ch÷ sè kh«ng ch¾c. Ch÷ sè ch¾c víi ω = 1 gäi lµ ch¾c theo nghÜa réng. Ch÷ sè ch¾c víi ω = 0, 56 gäi lµ ch¾c theo nghÜa hÑp. Chó ý: • NÕu βi lµ ch÷ sè ch¾c th× βj, ∀j ≥ i còng lµ ch÷ sè ch¾c. • NÕu βi kh«ng ch¾c th× βj, ∀j ≤ i còng kh«ng ch¾c. • Mét ch÷ sè lµ ch¾c sau khi thu gän sè cã thÓ nã kh«ng cßn lµ ch¾c. • Trong kü thuËt, ng−êi ta th−êng dïng ω = 1 vµ nÕu ch÷ sè lµ ch¾c th× sau thu gän nã vÉn lµ ch¾c (0, 56 ≤ ω ≤ 1). • Khi tÝnh to¸n, ta th−êng gi÷ l¹i c¸c ch÷ sè ch¾c vµ lÊy phô thªm tõ 1 ®Õn 2 ch÷ sè kh«ng ch¾c vµ cã ký hiÖu riªng ®Ó chØ c¸c ch÷ sè kh«ng ch¾c nµy.
  6. Gi¶i tÝch sè 5 • Sai sè t−¬ng ®èi cña mét sè kh«ng phô thuéc vµo vÞ trÝ dÊu phÈy cña nã (dÊu chÊm thËp ph©n). 1.4 Hai bµi to¸n vÒ sai sè XÐt sè gÇn ®óng viÕt ë d¹ng thËp ph©n p p−1 p−s a = ±(βp10 + βp−110 + + βp−s10 ). Cã hai bµi to¸n ®Æt ra: Bµi to¸n 1: 0 BiÕt sè ch÷ sè ch¾c cña a lµ γa, t×m sai sè t−¬ng ®èi δa cña a. Gäi a lµ sè a mµ sau khi dêi dÊu phÈy sao cho ch÷ sè ch¾c cuèi ë hµng ®¬n vÞ vµ toµn ch÷ sè ch¾c. Ta cã γa−1 0 γa−1 γa βp × 10 ≤ a ≤ (βp + 1) × 10 ≤ 10 . VËy 1 1 γ −1 ≤ δa ≤ γ −1 . (βp + 1) × 10 a βp × 10 1 NÕu kh«ng biÕt βp th× lÊy 1 1 ≤ δ ≤ . 10s a 10s−1 Bµi to¸n 2: BiÕt sai sè t−¬ng ®èi lµ δa, t×m sè ch÷ sè ch¾c γa. Gi¶ sö biÕt δa > 0, ta viÕt −m δa = λ10 víi 0.1 1 th× 4am ≤ 10 vµ am cã m ch÷ sè ch¾c.
  7. Gi¶i tÝch sè 6 λ Cuèi cïng ta cã thÓ kÕt luËn, nÕu δa = 10m , 0.1 < λ ≤ 1 vµ λ(βp + 1) ≤ 1 th× a cã m + 1 ch÷ sè ch¾c, ng−îc l¹i a cã m ch÷ sè ch¾c. 1.5 Sai sè c¸c phÐp to¸n Gi¶ sö ph¶i t×m ®¹i l−îng y theo c«ng thøc y = f(x1, x2, , xn). ∗ ∗ Gäi xi , y , i = 1, 2, , n vµ xi, y, i = 1, 2, , n lµ c¸c gi¸ trÞ ®óng vµ gÇn ®óng. NÕu f kh¶ vi liªn tôc ta cã ∗ ∗ ∗ |y − y | = |f(x1, , xn) − f(x1, , xn)| Xn |∂f(x , , θ , , x )| = 1 i n |x − x∗|, ∂x i i i=1 i ∗ ∗ ë ®©y θi ∈ [xi, xi ], i = 1, 2, , n. Ta cã thÓ coi (do f kh¶ vi liªn tôc vµ xi kh¸ gÇn xi), ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯∂f(x1, , θi, , xn)¯ ¯∂f(x1, , xn)¯ ¯ ¯ ' ¯ ¯ . ∂xi ∂xi Do ®ã ¯ ¯ Xn ¯∂f(x , , x )¯ 4 = ¯ 1 n ¯ 4 , y ¯ ∂x ¯ xi i=1 i vµ ¯ ¯ 4 Xn ¯∂ ln f(x , , x )¯ δ = y = ¯ 1 n ¯ 4 . y |y| ¯ ∂x ¯ xi i=1 i a. Sai sè phÐp tÝnh céng, trõ: Xn y = f(x1, x2 , xn) = xi, i=1 ∂f(x , x , x ) Xn 1 2 n = 1 ⇒ 4 = 4x . ∂x y i i i=1 Gi¶ sö 4xm = maxi=1,n{4xi }, vµ ch÷ sè ch¾c cuèi cña xm ë hµng thø k, (4xm = 10k). Ta cã: k 4y ≥ 4xm = 10 . Do ®ã khi lµm phÐp céng, trõ nªn qui trßn c¸c xi ®Õn møc gi÷ l¹i 1 hoÆc 2 ch÷ sè bªn ph¶i hµng thø k. Chó ý: Khi trõ hai sè gÇn nhau cÇn lÊy c¸c sè víi nhiÒu ch÷ sè ch¾c v× khi trõ hai sè gÇn nhau kÕt qu¶ mÊt chÝnh x¸c.
  8. Gi¶i tÝch sè 7 b. Sai sè phÐp to¸n nh©n, chia: Gi¶ sö x1, , xp y = = f(x1, , xp, , xn). xp+1, , xn Khi ®ã Xp Xn ln y = ln xi − ln xj i=1 j=p+1 suy ra Xn δy = δxi. i=1 NÕu δxm = maxi=1,n{δxi} vµ sè ch÷ sè ch¾c cña xm lµ k th× δy ≥ δxm vµ sè ch÷ sè ch¾c cña y kh«ng v−ît qu¸ k. V× vËy khi lµm phÐp to¸n nh©n, chia ta chØ cÇn lÊy k + 1 hoÆc k + 2 ch÷ sè lµ ®ñ. c. Sai sè phÐp lòy thõa, khai c¨n vµ nghÞch ®¶o: α Cho y = x , α ∈ R, ¯ ¯ ¯d ln y ¯ δy = ¯ ¯ 4 = |α|δx. ¯ dx ¯ x • NÕu α > 1 th× δy > δx tøc lµ phÐp lòy thõa lµm gi¶m ®é chÝnh x¸c. • NÕu 0 < α < 1 th× δy < δx tøc lµ phÐp khai c¨n lµm t¨ng ®é chÝnh x¸c. • NÕu α = −1 th× δy = δx vµ phÐp nghÞch ®¶o cã ®é chÝnh x¸c kh«ng ®æi.
  9. Gi¶i tÝch sè 8 Ch−¬ng 2 XÊp XØ Tèt NhÊt 2.1. XÊp xØ tèt nhÊt trong kh«ng gian ®Þnh chuÈn Gi¶ sö X lµ kh«ng gian tuyÕn tÝnh ®Þnh chuÈn. L ⊂ X lµ ®a t¹p tuyÕn tÝnh ®ãng cña X vµ f ∈ X. Bµi to¸n ®Æt ra h·y t×m phÇn tö f ∗ ∈ L sao cho: k f − f ∗ k= inf k g − f k . g∈L §Þnh lý 2.1.1 NÕu L lµ kh«ng gian con h÷u h¹n chiÒu cña X th× víi mäi f ∈ X lu«n tån t¹i f ∗ ∈ L tháa k f − f ∗ k= inf k g − f k . g∈L (PhÇn tö f ∗ gäi lµ phÈn tö xÊp xØ tèt nhÊt f trªn L). Chøng minh: XÐt Ω = {g ∈ L :k g k≤ 2 k f k} ⊂ L. DÔ thÊy Ω lµ tËp ®ãng, giíi néi trong kh«ng gian h÷u h¹n chiÒu nªn Ω lµ Compact. XÐt hµm φ(g) :=k f − g k . Ta cã |φ(g) − φ(h)| = |k f − g k − k f − h k| ≤k (f − g) − (f − h) k=k h − g k . Do φ lµ hµm liªn tôc trªn tËp Compact Ω nªn hµm φ ®¹t cùc tiÓu trªn Ω. Tõ ®ã ∃f ∗ ∈ Ω: φ(f ∗) = min φ(g). g∈Ω MÆt kh¸c: NÕu g ∈ L \ Ω tøc lµ g kh«ng thuéc Ω th× k g − f k≥k g k − k f k > 2 k f k − k f k=k f k=k f − θ k (ë ®©y θ chØ phÇn tö kh«ng cña kh«ng gian X). Bëi vËy ∀g ∈ L\Ω, th× k g−f k>k f−θ k, tøc lµ inf k g − h k≥k f − θ k . g∈L\Ω Suy ra k f − f ∗ k= min k f − g k g∈Ω
  10. Gi¶i tÝch sè 9 ≤k f − θ k ≤ inf k g − h k . g∈L\Ω Do ®ã k f − f ∗ k= min k f − g k . g∈L §Þnh lý ®−îc chøng minh. Chó ý: Sinh viªn cã thÓ tham kh¶o mét chøng minh kh¸c sau ®©y khi (trong ®Þnh lý trªn) ®· biÕt c¬ së cña kh«ng gian tuyÕn tÝnh L ®Ó thÊy râ h¬n ý nghÜa vÊn ®Ò. Gi¶ sö {g1, g2, , gn} lµ c¸c phÇn tö ®éc lËp tuyÕn tÝnh trong X. §Æt (bao tuyÕn tÝnh cña c¸c phÇn tö {g1, g2, , gn} trong X) Xn £{g1, g2, , gn} := { aigi, ai ∈ R}. i=1 DÔ thÊy £{g1, g2, , gn} lµ kh«ng gian con tuyÕn tÝnh h÷u h¹n chiÒu trong X. §Æt L = £{g1, g2, , gn}. XÐt phiÕn hµm Xn n F0(c) :=k cigi k, c = (c1, c2, , cn) ∈ R . i=1 Pn 1 2 2 n n KÝ hiÖu | c |= ( i=1 ci ) vµ ®Æt K = {c ∈ R , | c |= 1} th× K ⊂ R lµ tËp compact trong kh«ng gian h÷u h¹n chiÒu. Do F0(c) lµ hµm liªn tôc trªn tËp compact nªn ®¹t cùc tiÓu t¹i c0 ∈ K tøc lµ 0 ≤ m := F0(c0) = min F0(c). c∈K Pn Bëi m kh«ng thÓ lµ 0 v× m = 0 th× F0(c0) = i=1 c0igi = 0, tøc lµ c0i = 0, ∀i. §iÒu nµy kÐo theo | c0 |= 0 lµ m©u thuÉn (v× c0 ∈ K). XÐt hµm Xn F (c) =k cigi − f k . i=1 NÕu f ∈ L th× lÊy f ∗ = f. NÕu f kh«ng thuéc L th× inf F (c) = α > 0; c∈Rn Xn Xn F (c) =k cigi − f k≥k cigi k − k f k i=1 i=1 Xn c =| c |k i g k − k f k . | c | i i=1
  11. Gi¶i tÝch sè 10 ci ci ci §Æt c = ( |c| , |c| , , |c| ) th× | c |= 1, tøc lµ c ∈ K. Tõ trªn ta cã F (c) =| c | F0(c)− k f k≥ m | c | − k f k . DÔ thÊy r»ng m | c | − k f k→ ∞ khi | c |→ ∞. Theo ®Þnh nghÜa giíi h¹n, tån t¹i M > 0, ∀c ∈ Rn, | c |> M th× F (c) > α + 1. Bëi qu¶ cÇu ®ãng B(0,M) := {c ∈ Rn, | c |≤ M} lµ tËp compact trong Rn. H¬n n÷a F (c) lµ hµm liªn tôc nªn nã ®¹t cùc trÞ trªn B(0,M). Tøc lµ tån t¹i cˆ ∈ B(0,M) sao cho F (ˆc) = α. LÊy Xn ∗ f = cˆigi, i=1 dÔ thÊy f ∗ lµ phÇn tö xÊp xØ tèt nhÊt f trong L. 0 1 2 n VÝ dô: XÐt X = L2[0, 1]. xÐt hÖ hµm {g0 = x , g1 = x , g2 = x , , gn = x }. §Æt Xn i L := £{g1, g2, , gn} = aix , ai ∈ R} i=0 lµ tËp c¸c ®a thøc thùc bËc kh«ng qu¸ n vµ L lµ kh«ng gian con h÷u h¹n chiÒu cña L2[0, 1]. Theo §Þnh lý 2.1.1 víi mäi f ∈ L2[0, 1] lu«n tån t¹i ®a thøc bÆc kh«ng qu¸ n ∗ lµ Qn sao cho ∗ k f − Qn kL2[0,1]= min k f − g kL2[0,1] . g∈L Tøc lµ µZ ¶ 1 µZ ¶ 1 1 2 1 2 ∗ 2 2 |f(x) − Qn(x)| dx = min |f(x) − g(x)| dx . 0 g∈L 0 §Þnh nghÜa 2.1.2 Kh«ng gian tuyÕn tÝnh ®Þnh chuÈn X ®−îc gäi lµ låi chÆt (ngÆt) nÕu ∀x, y ∈ X, k x k=k y k= 1, k x + y k= 2, th× x = y. §Þnh lý 2.1.3 NÕu X lµ kh«ng gian låi chÆt vµ L lµ kh«ng gian con h÷u h¹n chiÒu cña X th× phÇn tö xÊp xØ tèt nhÊt f ∗ lµ duy nhÊt. Chøng minh: §Æt % = min k f − g k, g∈L
  12. Gi¶i tÝch sè 11 cã hai tr−êng hîp x¶y ra 1) Tr−êng hîp % = 0 ⇒ f ∈ L vµ f ∗ = f. Tøc f ∗ lµ duy nhÊt. ∗ ∗ ∗ ∗ 2) Tr−êng hîp % 6= 0 th× f∈ / L vµ % > 0. Gi¶ thiÕt ph¶n chøng, tån t¹i f1 vµ f2 , f1 6= f2 ®Òu lµ xÊp xØ tèt nhÊt f. Khi ®ã ∗ k f − f1 k= %, ∗ k f − f2 k= %. Ta cã: f ∗ + f ∗ k f − f ∗ k k f − f ∗ k % ≤k f − 1 2 k≤ 1 + 2 2 2 2 % % = + = %. 2 2 Suy ra f ∗ + f ∗ k f − 1 2 k= %. 2 ∗ ∗ (f1 +f2 ) Tõ ®ã phÇn tö 2 còng lµ phÇn tö xÊp xØ tèt nhÊt f trªn L. B©y giê ta xÐt hai phÇn f−f1 f−f2 tö trong X lµ 2 vµ 2 . DÔ kiÓm tra r»ng f − f ∗ f − f ∗ k 1 k = k 2 k = 1, % % vµ h¬n n÷a f − f ∗ f − f ∗ 2f − (f ∗ + f ∗) k 1 + 2 k =k 1 2 k % % % f ∗+f ∗ f − 1 1 2 f ∗ + f ∗ 2.% = 2 k 2 k = k f − 1 2 k= = 2. % % 2 % Bëi X lµ låi chÆt nªn f − f ∗ f − f ∗ 1 ≡ 2 . % % ∗ ∗ VËy f1 = f2 vµ ®Þnh lý ®−îc chøng minh. Chó ý: a. NÕu X lµ låi chÆt th× víi hai ®iÓm kh¸c nhau trªn mÆt cÇu ®¬n vÞ, ®o¹n th¼ng nèi hai ®iÓm ®ã kh«ng cã ®iÓm chung nµo kh¸c víi mÆt cÇu trõ chÝnh hai ®iÓm nµy (ý nghÜa h×nh häc cña kh«ng gian låi chÆt). b. Kh«ng gian h÷u h¹n chiÒu Rn vµ kh«ng gian Hilbert lµ låi chÆt. c. Kh«ng gian C[0,1] (kh«ng gian c¸c hµm liªn tôc trªn ®o¹n [0, 1]) kh«ng låi chÆt. ThËt vËy, chØ cÇn lÊy phÇn tö y1(x) = 1, y2(x) = x, ta cã y1, y2 ∈ C[0,1] vµ ky1k = 1, ky2k = 1. H¬n n÷a, dÔ thÊy k y1 + y2 k= maxx∈[0,1]|1 + x| = 2 nh−ng y1 6= y2, vËy kh«ng gian
  13. Gi¶i tÝch sè 12 C[0,1]] kh«ng låi chÆt. d. NÕu tån t¹i phÇn tö xÊp xØ tèi nhÊt f ∗ cña f ta ®Æt kf − f ∗k := En(f). 2.2 XÊp xØ tèt nhÊt trong kh«ng gian c¸c hµm liªn tôc C[a,b] Ký hiÖu C[a,b] lµ kh«ng gian c¸c hµm liªn tôc trªn [a, b] vµ L lµ tËp mäi ®a thøc bËc kh«ng qu¸ n. §Þnh lý 2.2.1 (Wallee' - Poussin) Gi¶ sö f ∈ C[a,b] vµ Qn ∈ L. NÕu tån t¹i n + 2 ®iÓm ph©n biÖt a ≤ x0 0 ta chøng minh b»ng ph¶n chøng. Gi¶ sö ng−îc l¹i En(f) < µ = min |f(xi) − Qn(xi)|. i=0,n+1 XÐt P ∈ L lµ xÊp xØ tèt nhÊt f trªn L. Khi ®ã: k f − P k= En(f) < min |f(xi) − Qn(xi)|. i=0,n+1 Ta cã |P (xi) − f(xi)| ≤k P − f k < min |f(xi) − Qn(xi)| i ≤ |Q(xi) − f(xi)|. Suy ra sign[Q(xi) − P (xi)] = sign{[Q(xi) − f(xi)] + [f(xi) − P (xi)]}
  14. Gi¶i tÝch sè 13 = sign[Q(xi) − f(xi)], i = 0, 1, 2, , n + 1. Tõ ®ã ®a thøc bËc n lµ (Qn − P ) ®æi dÊu n + 2 lÇn trªn [a, b] nªn nã cã Ýt nhÊt (n + 1) nghiÖm, vËy Qn(x) ≡ P (x). XÐt µ = min |f(xi) − Qn(xi)| > max |f(x) − Qn(x)| i=0,n+1 x∈[a,b] ≥ min |f(xi) − Qn(xi)| = µ. i=0,n+1 §iÒu nµy lµ m©u thuÉn vµ ®Þnh lý ®−îc chøng minh. §Þnh lý sau ®©y lµ kh¸ quan träng vÒ phÇn tö xÊp xØ tèt nhÊt trong C[a,b] v× r»ng ngoµi viÖc nã chØ ra ®−îc phÇn tö xÊp xØ tèt nhÊt cña f liªn tôc mµ nã cßn cho ta c¸ch x¸c ®Þnh ®a thøc xÊp xØ tèt nhÊt Qn(x). §Þnh lý 2.2.2 (Chebyshev) §iÒu kiÖn cÇn vµ ®ñ ®Ó Qn lµ ®a thøc bËc kh«ng qu¸ n xÊp xØ tèt nhÊt cña f ∈ C[a,b] lµ tån t¹i (n + 2) ®iÓm ph©n biÖt, a ≤ x0 < x1 < < xn+1 ≤ b, sao cho i f(xi) − Qn(xi) = α(−1) k f − Q k, i = 0, 1, 2, , n + 1, α = ±1. n+1 (Víi α = 1 hoÆc α = −1 vµ kh«ng phô thuéc vµo i. D·y ®iÓm {xi}i=0 ®­îc gäi lµ d·y ®iÓm Chebyshev.) §Þnh lý nµy cã chøng minh kh¸ phøc t¹p. Chøng minh chi tiÕt sinh viªn cã thÓ t×m trong c¸c tµi liÖu tham kh¶o. D−íi ®©y chØ tr×nh bµy ng¾n gän ®Ó ng−êi ®äc h×nh dung ý t−ëng vµ kü thuËt cña ph−¬ng ph¸p chøng minh. a. §iÒu kiÖn ®ñ: §Æt ν =k f − Qn k, µ = min |f(xi) − Qn(xi)|. i=0,n+1 Tõ gi¶ thiÕt vµ §Þnh lý Wallee'‐Poussin ta cã ν = µ = min |f(xi) − Qn(xi)| i ≤ En(f) ≤k f − Qn k= µ. VËy En(f) =k f − Qn k .
  15. Gi¶i tÝch sè 14 Tøc lµ Qn lµ ®a thøc xÊp xØ tèt nhÊt f. b. §iÒu kiÖn cÇn. Ta x©y dùng n + 2 ®iÓm Chebyshev nh− sau ν =k f − Qn k= En(f). §Æt g = f − Qn vµ lÊy y0 = a, y1 = min{y :k g(y) k= ν}. Kh«ng mÊt tæng qu¸t, xem g(y1) = ν. y2 = min {y : g(y) = −ν}; y∈[y1,b] m ym = min {y : g(y) = (−1) ν}. y∈[ym−1,b] m Nh− vËy ta ®∙ x©y dùng ®−îc d∙y {yn}n=0 b»ng quy n¹p. NÕu m < n + 2 th× b»ng c¸ch x©y dùng c¸c d·y phï hîp ng−êi ta chøng minh ®−îc r»ng tr−êng hîp nµy kh«ng x¶y ra. VËy m ≥ n + 2. Khi ®ã ta chØ cÇn lÊy {y0, y1, , yn+1} lµm d∙y ®iÓm Chebyshev vµ §Þnh lý ®−îc chøng minh. Ta ®∙ biÕt kh«ng gian C[a,b] kh«ng låi chÆt nªn vÊn ®Ò ®Æt ra lµ liÖu ®Þnh lý duy nhÊt vÒ phÇn tö xÊp xØ tèt nhÊt cßn ®óng trong C[a,b] kh«ng? C©u tr¶ lêi lµ vÉn ®óng. §iÒu ®ã ®−îc chØ ra trong ®Þnh lý sau: §Þnh lý 2.2.3 §a thøc xÊp xØ ®Òu tèt nhÊt cña f ∈ C[a,b] trªn L lµ duy nhÊt. Chøng minh: Gi¶ sö Pn ∈ L, Qn ∈ L ®Òu lµ c¸c ®a thøc xÊp xØ tèt nhÊt cña f vµ Pn 6= Qn. XÐt ®a thøc P + Q n n ∈ L, 2 ta cã P + Q E (f) ≤k n n − f k n 2 1 1 ≤ k f − P k + k f − Q k 2 n 2 n 1 1 = E (f) + E (f) = E (f). 2 n 2 n n VËy P + Q k n n − f k= E (f). 2 n
  16. Gi¶i tÝch sè 15 Pn+Qn §iÒu nµy suy ra ®a thøc 2 còng lµ ®a thøc xÊp xØ tèt nhÊt f trªn L. Gi¶ sö d·y n+1 Pn+Qn {xi}i=0 lµ d·y Chebyshev øng víi 2 th× ¯ ¯ ¯P (x ) + Q (x ) ¯ ¯ n i n i − f(x )¯ = E (f), i = 0, 1, 2, , n + 1. ¯ 2 i ¯ n Bëi vËy 2En(f) = |P (xi) − f(xi) + Q(xi) − f(xi)| ≤ |P (xi) − f(xi)| + |Q(xi) − f(xi)| ≤k P − f k + k Q − f k= 2En(f). Tõ ®ã, |P (xi) − f(xi)| = |Q(xi) − f(xi)| = En(f), ∀i. Suy ra P (xi) − f(xi) = λi(Q(xi) − f(xi)), λi = ±1. Ta cã, 2En(f) = |P (xi) − f(xi) + λi(P (xi) − f(xi))| = (1 + λi)|P (xi) − f(xi)|. Suy ra 1 + λi = 2 tøc lµ λi = 1. Cuèi cïng ta cã: Pn(xi) − f(xi) = Qn(xi) − f(xi), ∀i ⇒ Pn(xi) = Qn(xi), ∀i. Bëi Pn(x) vµ Qn(x) lµ c¸c ®a thøc bËc n trïng nhau trªn n + 2 ®iÓm nªn Pn(x) = Qn(x) vµ ®Þnh lý ®­îc chøng minh. §Þnh lý 2.2.4 XÊp xØ tèt nhÊt cña mét hµm ch¼n (lÎ) còng lµ mét hµm ch¼n (lÎ). Chøng minh: Gi¶ sö f lµ ch¼n th× khi thay x bëi −x ta nhËn ®­îc ∗ ∗ | f(−x) − f (−x) |=| f(x) − f (−x) |≤ En(f), ∀x. Tõ ®ã f ∗(−x) còng lµ xÊp xØ tèt nhÊt f. Bëi phÇn tö xÊp xØ tèt nhÊt lµ duy nhÊt ta suy ra f ∗(x) = f ∗(−x), ∀x. Tøc lµ f ∗ lµ hµm ch½n. a. XÊp xØ ®a thøc bËc kh«ng Q0(x) Cho f ∈ C[a, b]. H·y t×m ®a thøc bËc kh«ng Q0(x) xÊp xØ tèt nhÊt hµm liªn tôc f trªn ®o¹n [a, b]. §Æt m := min f(x),M := max f(x). x∈[a,b] x∈[a,b] Khi ®ã m ≤ f(x) ≤ M, ∀x ∈ [a, b].
  17. Gi¶i tÝch sè 16 M+m Bëi Q0(x) lµ ®a thøc bËc kh«ng tøc lµ hµm h»ng nªn ta lÊy Q0(x) = 2 vµ chØ ra r»ng ®a thøc nµy chÝnh lµ ®a thøc xÊp xØ tèt nhÊt f(x). Ta cã M − m M − m − ≤ f(x) − Q (x) ≤ , 2 0 2 vËy M − m | f(x) − Q (x) |≤ , ∀x ∈ [a, b]. 0 2 Gi¶ sö f(x0) = m, f(x1) = M, x0, x1 ∈ [a, b]. DÔ thÊy r»ng x0 vµ x1 lµ d·y ®iÓm Chebyshev bëi M − m f(x ) − Q (x ) = − , 0 0 0 2 M − m f(x ) − Q (x ) = . 1 0 1 2 Theo §Þnh lý Chebyshev, Q0 lµ xÊp xØ tèt nhÊt cña f trªn [a, b]. b. XÊp xØ tèt nhÊt ®a thøc bËc mét Q1(x) XÐt hµm f(x) låi liªn tôc trªn [a, b]. NÕu f(x) lµ tuyÕn tÝnh th× ®a thøc xÊp xØ tèt nhÊt còng lµ f(x). Gi¶ sö f(x) kh«ng lµ hµm tuyÕn tÝnh vµ Q1(x) = px + q lµ ®a thøc xÊp xØ tèt nhÊt f(x). §Æt U(x) := f(x) − (px + q) th× U(x) còng lµ hµm låi nªn ®¹t cùc trÞ t¹i ®iÓm c ∈ [a, b] duy nhÊt. Theo §Þnh lý Chebyshev th× cã ba ®iÓm Chebyshev lu©n phiªn, vËy hai ®iÓm ®Çu vµ cuèi ph¶i lµ a vµ b. §iÓm cßn l¹i lµ ®iÓm c ∈ (a, b) mµ t¹i ®ã U(x) ®¹t cùc trÞ. Ta cã U(a) = f(a) − (pa + q) = α k f − Q1 k, U(c) = f(c) − (pc + q) = −α k f − Q1 k, U(b) = f(b) − (pb + q) = α k f − Q1 k; α = ±1. Tõ U(b) − U(a) = f(b) − f(a) − p(b − a) = 0. Suy ra f(b) − f(a) p = . b − a §Ó tÝnh q ta xÐt 0 = U(a) + U(c) = f(a) − (pa + q) + f(c) − (pc + q)
  18. Gi¶i tÝch sè 17 = f(a) + f(c) − p(a + c) − 2q. VËy f(b) − f(a) 2q = f(a) + f(c) − (a + c) b − a Suy ra f(a) + f(c) (f(b) − f(a))(a + c) q = − . 2 2(b − a) Cuèi cïng ta dÔ kiÓm tra r»ng ®a thøc Q1(x) = px + q tháa c¸c ®iÒu kiÖn cña ®Þnh lý Chebyshev. 2.3 XÊp xØ tèt nhÊt trong kh«ng gian Hilbert ∞ XÐt kh«ng gian Hilbert H vµ {ei}i=1 lµ hÖ trùc chuÈn ®Çy ®ñ, tøc lµ = δij, i, j ∈ N vµ Span(ei) = H. Víi mçi x ∈ H lËp tæng Fourier Xn Sn := ciei, i=1 ë ®©y ci := lµ hÖ sè Fourier cña x. Víi mçi n ∈ N, 2 2 2 0 ≤k x − Sn k =k x k −2 + k Sn k Xn 2 2 =k x k − ci . i=1 VËy Xn 2 2 ci ≤k x k , ∀n ∈ N. i=1 Pn 2 §iÒu nµy chØ ra chuçi i=1 ci héi tô vµ cã bÊt ®¼ng thøc Bessel X∞ 2 2 ci ≤k x k . i=1 P∞ P∞ Chóng ta ®· biÕt lµ chuçi Fourier i=1 ciei héi tô vµ h¬n n÷a x = i=1 ciei. B©y giê, gi¶ sö H0 lµ mét kh«ng gian con ®ãng cña kh«ng gian Hilbert H vµ x ∈ H. Bµi to¸n ®Æt ra lµ t×m h0 ∈ H0 sao cho k x − h0 k= inf k x − h0 k= d(x, H0). h∈H0
  19. Gi¶i tÝch sè 18 Gi¶ sö h0 = arg minh∈H0 k x − h0 k vµ cè ®Þnh phÇn tö h ∈ H0 bÊt kú. Víi α ∈ R xÐt hµm 2 F (α) :=k x − h0 + αh k . §¹o hµm cña F lµ 0 2 F (α) = 2 +2α k h k . Râ rµng r»ng 2 F (0) = min F (α) =k x − h0 k . α∈R 0 Bëi vËy F (0) = 0, tøc lµ = 0 víi mäi h ∈ H0. §iÒu nµy chØ ra phÇn tö x − h0 trùc giao víi H0, (x − h0)⊥H0. H¬n n÷a, h0 = arg min k x − h0 k . h∈H0 Thùc vËy víi mäi h ∈ H0, ta cã 2 2 k x − h k =k (x − h0) + (h0 − h) k 2 2 2 =k x − h0 k + k h0 − h k ≥k x − h0 k . Tøc lµ h0 = arg minh∈H0 k x − h0 k. DÊu b»ng chØ x¶y ra khi vµ chØ khi h = h0. DÔ thÊy r»ng nÕu kh«ng gian H0 cã sè chiÒu h÷u h¹n th× phÇn tö xÊp xØ tèt nhÊt h0 = arg minh∈H0 k x − h0 k tån t¹i vµ duy nhÊt.
  20. Gi¶i tÝch sè 19 Ch−¬ng 3 XÊp XØ Hµm B»ng §a Thøc Néi Suy Cho [a, b] ⊂ R. Gäi f(x), x ∈ [a, b] lµ hµm cÇn xÊp xØ, φ0(x), φ1(x), , φn(x) lµ hÖ hµm ®éc lËp tuyÕn tÝnh. §Æt ( ) Xn Rn = φ(x) = aiφi(x), ai ∈ R . i=0 3.1 Bµi to¸n néi suy Cho f(x) ∈ R, xi ∈ [a, b], (i = 0, n) lµ c¸c ®iÓm ph©n biÖt trªn [a, b]. Tøc lµ a ≤ x0 < x1 < x2 < < xn−1 < xn ≤ b. Bµi to¸n ®Æt ra, h·y x¸c ®Þnh hµm φ(x) ∈ Rn sao cho f(xi) = φ(xi) (c¸c ®iÓm xi gäi lµ mèc néi suy). §Ó gi¶i bµi to¸n trªn chØ cÇn t×m c¸c gi¸ trÞ a0, a1, , an sao cho Pn f(xi) = j=0 ajφj(xi). Ta ®· biÕt nÕu   ϕ0(x0) ϕ1(x0) ϕn(x0)  ϕ (x ) ϕ (x ) ϕ (x )  rank  0 1 1 1 n 1  < n + 1,   ϕ0(xn) ϕ1(xn) ϕn(xn) th× bµi to¸n néi suy nãi trªn kh«ng cã lêi gi¶i (v× ®Þnh thøc 4 = 0). VÊn ®Ò ®Æt ra lµ n t×m hÖ hµm {φk(xi)}k=0 nh­ thÕ nµo ®Ó víi mäi mèc néi suy xi th× bµi to¸n cña ta cã lêi gi¶i. n §Þnh nghÜa 3.1.1 HÖ hµm {φi(x)}i=0 ®−îc gäi lµ hÖ Chebyshev, nÕu víi mäi d·y Pn c0, c1, c2, , cn kh«ng ®ång thêi b»ng kh«ng th× hµm x¸c ®Þnh bëi P (x) := i=0 ciφi(x) cã kh«ng qu¸ n nghiÖm trªn [a, b]. n i n VÝ dô: XÐt hÖ hµm {φi(x)}i=0, φi(x) = x th× hÖ {φi(x)}i=0 lµ Chebyshev v× theo ®Þnh lý Taylor, c¸c ®a thøc bËc kh«ng qu¸ n cã kh«ng qu¸ n nghiÖm trªn tr­êng sè thùc. n Chó ý: NÕu hÖ hµm {φi(x)}i=0 lµ Chebyshev th× nã lµ hÖ hµm ®éc lËp tuyÕn tÝnh. (®iÒu ng−îc l¹i ch−a ch¾c ®óng). §Þnh lý 3.1.2 NÕu víi mçi i = 0, 1, 2, , n c¸c hµm φi(x) lµ kh¶ vi liªn tôc ®Õn cÊp
  21. Gi¶i tÝch sè 20 n + 1 trªn [a, b] vµ víi mäi k = 0, 1, 2, , n cã ®Þnh thøc Wronskian:   ϕ0(x) ϕ1(x) ϕn(x)  ϕ(1)(x) ϕ(1)(x) ϕ(1)(x)  W [φ , φ , , φ ] =  0 1 n  6= 0, 0 1 k   (n) (n) (n) ϕ0 (x) ϕ1 (x) ϕn (x) n víi mäi x ∈ [a, b]. Khi ®ã hÖ hµm {ϕi}i=0 lµ hÖ hµm Chebyshev. n §Þnh lý 3.1.3 Víi mäi d·y ®iÓm {xi}i=0 lµ c¸c mèc néi suy, víi mäi hµm f(x) th×, n Tån t¹i ®a thøc néi suy khi vµ chØ khi hÖ hµm {ϕi}i=0 lµ hÖ hµm Chebyshev. Chøng minh: Tõ bµi to¸n néi suy ta suy ra ®Ó cã ®a thøc néi suy ta ph¶i gi¶i hÖ ®¹i sè sau: ½ Pn i=0 ciϕi(xj) = f(xj) j = 0, n §Ó hÖ gi¶i ®−îc (cã nghiÖm) th× ®Þnh thøc ¯ ¯ ¯ ¯ ¯ ϕ0(x0) ϕ1(x0) ϕn(x0) ¯ ¯ ¯ ¯ ϕ0(x1) ϕ1(x1) ϕn(x1) ¯ 4 = ¯ ¯ 6= 0, ¯ ¯ ¯ ¯ ϕ0(xn) ϕ1(xn) ϕn(xn) n víi mäi d·y ®iÓm {xi}i=0 vµ xi 6= xj, i 6= j. n a. Gi¶ sö {ϕi}i=0 lµ hÖ Chebyshev ta chøng minh 4 6= 0. Gi¶ sö 4 = 0 khi ®ã Pn 2 Pn tån t¹i αj, j = 0, 1, 2, , n mµ j=0 αj > 0 sao cho j=0 αjϕj(xi) = 0, nªn hµm Pn n P (x) = i=0 αjϕj(xi) cã (n + 1) nghiÖm vµ ®iÒu nµy lµ v« lý v× hÖ {ϕi}i=0 lµ hÖ Chebyshev. n b. Víi mçi hµm f, víi mçi {xi}i=0, xi 6= xj, i 6= j mµ tån t¹i ®a thøc néi suy, ta n n chøng minh hÖ {ϕi}i=0 lµ hÖ Chebyshev. Gi¶ sö ng−îc l¹i r»ng hÖ {ϕi}i=0 kh«ng lµ hÖ Pn Chebyshev, tõ ®ã tån t¹i hµm P (x) = i=0 ciϕi(x) cã n + 1 nghiÖm trªn ®o¹n [a, b] mµ ta cã thÓ s¾p xÕp c¸c nghiÖm ®ã sao cho a ≤ x0 0 nªn 4 = 0, tøc lµ hÖ ®¹i sè hoÆc v« nghiÖm hoÆc v« ®Þnh lµ m©u thuÉn, vµ ®Þnh lý ®−îc chøng minh.
  22. Gi¶i tÝch sè 21 3.2 Gi¶i hÖ ®¹i sè tuyÕn tÝnh x¸c ®Þnh ®a thøc néi suy Tõ hÖ ®¹i sè x¸c ®Þnh ®a thøc néi suy, nÕu ma trËn hÖ sè cã ®Þnh thøc ¯ ¯ ¯ ¯ ¯ ϕ0(x0) ϕ1(x0) ϕn(x0) ¯ ¯ ¯ ¯ ϕ0(x1) ϕ1(x1) ϕn(x1) ¯ 4 = ¯ ¯ 6= 0. ¯ ¯ ¯ ¯ ϕ0(xn) ϕ1(xn) ϕn(xn) §Æt ¯ ¯ ¯ ¯ ¯ ϕ0(x0) f(x0) ϕn(x0) ¯ ¯ ¯ ¯ ϕ0(x1) f(x1) ϕn(x1) ¯ 4i = ¯ ¯ , ¯ ¯ ¯ ¯ ϕ0(xn) f(xn) ϕn(xn) 4i vµ sö dông ph−¬ng ph¸p Cramer ®Ó gi¶i hÖ th× nghiÖm sÏ lµ ci = 4 . Tõ ®ã ta cã Xn Xn 4 Q (x) = c ϕ (x) = i ϕ (x). n i i 4 i i=0 i=0 Khai triÓn ®Þnh thøc ∆i trªn theo cét thø i ta nhËn ®−îc Xn 4i = f(xj)4ij, j=0 víi 4ij lµ phÇn bï ®¹i sè cña f(xj). ThÕ ®Þnh thøc 4i vµo c«ng thøc tÝnh Qn(x) ta nhËn ®−îc X 4 Q (x) = ji f(x )ϕ (x) n 4 j i i,j à ! Xn Xn 4 Xn = f(x ) ji ϕ (x) = f(x )φ (x). j 4 i j j j=0 i=0 j=0 Bëi vËy, ta cã Xn Qn(x) = f(xj)φj(x). j=0 NhËn xÐt: a. Víi mçi hµm f(x) do Qn(x) lµ ®a thøc néi suy cña f(x) nªn Qn(xj) = Pn f(xj) = j=0 f(xj)φj(x), suy ra φj(xi) = δij, ∀i, j. b. Chän f(x) ≡ 1 th× f(xj) = 1 víi mäi j ta suy ra Xn φj(xi) = 1. i=0
  23. Gi¶i tÝch sè 22 Chó ý: CÇn quan t©m ®Õn c¸c vÊn ®Ò sau: 1. Trong c¸c bµi to¸n thùc tÕ kh¸c nhau, cÇn chän c¸c hÖ Chebyshev φi thÕ nµo cho phï hîp? 2. §é lÖch gi÷a hµm néi suy vµ ®a thøc néi suy? 3. Chän mèc néi suy nµo ®Ó cã lîi nhÊt? 4. §é ¶nh h−ëng cña sai sè vµ phÐp ®o? 3.3 §a thøc néi suy Lagrange n n Trong bµi to¸n néi suy nÕu lÊy hÖ Chebyshev lµ hÖ hµm {φi(x)}i=0 = {1, x, , x } th× ®a thøc néi suy Pn(x) cña hµm cÇn néi suy f(x) cã d¹ng: Xn i Pn(x) = cix . i=0 Bµi to¸n néi suy quy vÒ bµi to¸n: T×m ®a thøc Pn(x) sao cho: ½ Pn(xj) = yj, j = 0, 1, 2, , n. §Ó x¸c ®Þnh ®a thøc Pi(x) bËc n tháa Pi(xj) = δij. Khi ®ã Pi(x) cã d¹ng Pi(x) = A(x − x0)(x − x1) (x − xi−1)(x − xi+1) (x − xn). Do 1 = Pi(xi) = A(xi − x0)(xi − x1) (xi − xi−1)(xi − xi+1) (xi − xn), suy ra (x − x0)(x − x1) (x − xi−1)(x − xi+1) (x − xn) Pi(x) = . (xi − x0)(xi − x1) (xi − xi−1)(xi − xi+1) (xi − xn) VËy Xn Pn(x) = yiPi(x). i=0 §a thøc néi suy Pn(x) x¸c ®Þnh nh− trªn gäi lµ ®a thøc néi suy Lagrange. VÝ dô: XÐt hµm f cho d−íi d¹ng b¶ng sau x 0 2 3 5 f(x) 1 3 2 5 T×m ®a thøc néi suy Lagrange cña f.
  24. Gi¶i tÝch sè 23 Gi¶i: X¸c ®Þnh Pi(x), i = 0, 3 nh− sau: (x − 2)(x − 3)(x − 5) 1 P (x) = = − (x − 2)(x − 3)(x − 5), 0 (0 − 2)(0 − 3)(0 − 5) 30 x(x − 3)(x − 5) 1 P (x) = = x(x − 3)(x − 5), 1 2(2 − 3)(2 − 5) 6 x(x − 3)(x − 5) 1 P (x) = = − x(x − 2)(x − 5), 2 3(3 − 2)(3 − 5) 6 x(x − 2)(x − 3) 1 P (x) = = x(x − 2)(x − 3). 3 5(5 − 3)(5 − 2) 30 §a thøc néi suy lµ: Pm(x) = 1P0(x) + 3P1(x) + 2P2(x) + 5P3(x) 1 1 1 1 = − (x−2)(x−3)(x−5)+3 x(x−3)(x−5)−2 x(x−2)(x−5)+5 x(x−2)(x−3) 30 6 6 30 1 1 1 1 = − (x−2)(x−3)(x−5)+ x(x−3)(x−5)− x(x−2)(x−5)+ x(x−2)(x−3). 30 2 3 6 3.4 Tr−êng hîp c¸c mèc néi suy c¸ch ®Òu Trong néi suy Lagrange nÕu c¸c mèc néi suy c¸ch ®Òu nhau, tøc lµ x1 − x0 = x2 − x1 = = xn − xn−1 = h. Khi ®ã x1 = x0 + h; x2 = x1 + h xn = x0 + nh. §Æt x − x t := 0 . h Suy ra (x − x0) (x − xi−1)(x − xi+1) (x − xn) φi(x) = (xi − x0) (xi − xi−1)(xi − xi+1) (xi − xn) ht(th − h) (th − (i − 1)h)(th − (i + 1)h) (th − nh) = ih(ih − h) (ih − (i − 1)h)(ih − (i + 1)h) (ih − nh) (−1)n−i.t(t − i) (t − m) = i!(n − i)!(t − i) (−1)nt(t − 1) (t − n) Xn Ci f(x ) = (−1)i n i . n! t − i i=0 VËy, ta cã c«ng thøc (−1)nt(t − 1) (t − n) Xn Ci f(x ) P (x) = (−1)i n i . n n! t − i i=0
  25. Gi¶i tÝch sè 24 NhËn xÐt: n−i i (−1) Cn a. HÖ sè t−i kh«ng phô thuéc vµo hµm y = f(x). Nªn ta cã thÓ tÝnh s½n vµ lËp thµnh b¶ng ®Ó tÝnh. b. NÕu thªm mèc néi suy míi th× ph¶i tÝnh l¹i tõ ®Çu. x VÝ dô 1: T×m ®a thøc néi suy trïng víi y = 3 t¹i c¸c ®iÓm x0 = −1; x1 = 0; x2 = 1. x -1 0 1 1 . y 3 1 3 1 x(x − 1) (x + 1)(x − 1) (x + 1)x Q (x) = + 1 + 3 . 2 3 −1(−1 − 1) 1(0 − 1) (1 + 1).1 1 3 = (x2 − x) − (x2 − 1) + (x2 + x) 3 2 4 8 2 4 = x2 + x + 1 = x2 + x + 1. 6 6 3 3 Tõ ®ã 2 4 Q (x) = x2 + x + 1. 2 3 3 3.5 Sai sè cña c«ng thøc néi suy Lagrange (n+1) Cho f ∈ C[a,b] . X¸c ®Þnh sai sè R(x) = f(x) − Pn(x). Gi¶ sö Xn i Pn(x) = cix , i=0 lµ ®a thøc néi suy Lagrange cña f(x) trªn c¸c mèc a ≤ x0 < x1 < < xn ≤ b, tøc lµ P (xi) = yi, i = 0, 1, 2 , n. Gäi n ω(x) = Πi=0(x − xi) = (x − x0)(x − x1) (x − xn). B©y giê lÊy x ∈ [a, b] tïy ý, ta cè ®Þnh gi¸ trÞ x nµy vµ xem víi mäi i th× x 6= xi (v× nÕu x = xi th× sai sè lµ 0). XÐt hµm ϕ(z) = f(z) − Pn(z) − kω, k = Const. T¹i ®iÓm xi, cã ϕ(xi) = f(xi) − P (xi) − kω(xi), i = 0, n. Chän k ®Ó ϕ(x) = 0, khi ®ã ta cã −P (x) + f(x) k = n . ω(x)
  26. Gi¶i tÝch sè 25 DÔ thÊy r»ng ϕ(z) = 0 t¹i (n + 2) ®iÓm lµ x0, x1, , xn, x. Tõ ®ã suy ra: §¹o hµm bËc 1, ϕ(1)(z) = 0 t¹i (n + 1) ®iÓm; §¹o hµm bËc 2, ϕ(2)(z) = 0 t¹i n ®iÓm; §¹o hµm bËc n, ϕ(n)(z) = 0 t¹i 2 ®iÓm; Cuèi cïng sÏ tån t¹i ®iÓm ξ = ξ(x) ∈ [a, b] sao cho ϕ(n+1)(ξ) = 0. Tõ ®¹o hµm cÊp n + 1 cña ϕ(z) suy ra 0 = ϕ(n+1)(ξ) = f (n+1)(ξ) − k(n + 1)!. VËy f (n+1)(ξ) k = , (n + 1)! f(x) − P (x) k = n . ω(x) Nh− vËy f (n+1)(ξ) f(x) − P (x) = n . (n + 1)! ω(x) Tõ ®ã ta cã f (n+1)(ξ) R(x) = f(x) − P (x) = Πn (x − x ). n (n + 1)! i=0 i NÕu ®Æt: (n+1) Mn+1 = sup f (x). x∈[a,b] Suy ra: M |f(x) − P (x)| ≤ | n+1 Πn (x − x )|. n (n + 1)! i=0 i VÝ dô 2: Trong VÝ dô 1, ta ®· x¸c ®Þnh ®−îc ®a thøc néi suy hµm y = 3x t¹i c¸c mèc 2 2 4 néi suy {−1, 0, 1} lµ P2(x) = 3 x + 3 x + 1. B©y giê, ta x¸c ®Þnh sai sè t¹i x. Sö dông c«ng thøc sai sè ta cã R2 = f(x) − P2(x) f (3)(ξ) = [(x − x )(x − x )(x − x )]. 3! 0 1 2 NÕu ®Æt M = sup |f (3)(x)| = 3(ln3)3. x∈[−1,1] Khi ®ã sai sè cho bëi 3 |R | ≤ (ln3)3|Π2 (x − x )|. 2 2 i=0 i
  27. Gi¶i tÝch sè 26 3.6 Chän mèc néi suy tèi −u (n+1) Cho hµm f(x) ∈ C[a,b] vÊn ®Ò ®Æt ra lµ chän c¸c mèc néi suy nh− thÕ nµo ®Ó sai sè trong c«ng thøc néi suy lµ bÐ nhÊt? 1. §a thøc Chebyshev XÐt ®a thøc bËc n x¸c ®Þnh bëi Tn(x) = cos[n arccos(x)], trong ®ã n = 0, 1, 2, , vµ x ∈ [−1, 1]. §Ó thÊy ®−îc d¹ng hiÖn cña ®a thøc ta ®Æt θ = arccos(x) t−¬ng ®−¬ng cos θ = x. Thay vµo biÓu thøc ta cã: Tn±1(x) = cos[(n ± 1)θ] = cos nθ cos θ ∓ sin nθ sin θ. Suy ra Tn+1(x) + Tn−1(x) = 2xTn(x). Ta nhËn ®−îc c«ng thøc ®Ó tÝnh nh− sau Tn+1(x) = 2xTn(x) − Tn−1(x). Víi n = 0, 1, 2, , +∞, ta nhËn ®−îc T0(x) = cos0 = 1; T1(x) = x; 2 T2(x) = 2xT1(x) − T0(x) = 2 ∗ x − 1, Tn+1(x) = 2xTn(x) − Tn−1(x). n−1 NhËn xÐt: §a thøc Tn(x) lµ ®a thøc bËc n cã hÖ sè ®Çu lµ 2 . Tn(x) §Þnh lý 3.6.1 Trong tÊt c¶ c¸c ®a thøc bËc n víi hÖ sè ®Çu lµ 1 th× ®a thøc 2n−1 cã ®é lÖch so víi 0 nhá nhÊt trªn [−1, 1] (hÖ sè ®Çu hiÓu lµ hÖ sè cña sè h¹ng bËc cao nhÊt trong ®a thøc), tøc lµ víi mäi ®a thøc n n−1 P (x) = x + a1x + + an, th× T 1 k P k≥k n k= . 2n−1 2n−1
  28. Gi¶i tÝch sè 27 Chøng minh: Theo c¸ch x¸c ®Þnh cña ®a thøc Chebyshev ta cã T (x) cos[n arccos x] 1 | n | = | | ≤ . 2n−1 2n−1 2n−1 §iÒu nµy cã T (x) 1 | n | = , 2n−1 2n−1 suy ra nθ = kπ, tøc lµ kπ θ = , k = 0, 1, 2, , n. n Do ®ã kπ kπ arccos x = ⇒ x = cos( ). k n k n B©y giê xÐt ®a thøc T (x ) (−1)k Q(x) = n k − P (x ) = − P (x ). 2n−1 k 2n−1 k Tõ gi¶ thiÕt ph¶n chøng ta cã: 1 |P (x )| ≤k P k< . k 2n−1 (−1)k §iÒu nµy dÉn ®Õn dÊu cña biÕu thøc Q(xk) chØ phô thuéc vµo dÊu cña biÓu thøc 2n−k , tøc lµ (−1)k Sign(Q(x )) = Sign[ ], k = 0, 1, 2, , n. k 2k−1 VËy ®a thøc Q(xk) ®æi dÊu n + 1 lÇn nªn Q(x) cã Ýt nhÊt n nghiÖm trªn [a, b] lµ ®iÒu v« lý (bëi Q(x) cã bËc kh«ng qu¸ n). 2. NghiÖm cña ®a thøc Chebyshev XÐt ®iÓm xk lµ nghiÖm cña Tn(x) nghÜa lµ Tn(xk) = 0. Bëi Tn(x) = cos[n arccos(x)] (2k+1)π vµ theo c¸ch ®Æt θk = arccos(xk) nªn xk = cos(θk), suy ra θk = 2n . VËy 2k + 1 x = cos( )π, k = 0, 1, , n − 1. k 2n 3. NghiÖm cña ®a thøc Chebyshev trªn ®o¹n [a, b]
  29. Gi¶i tÝch sè 28 B©y giê xÐt x ∈ [a, b]. Tõ c«ng thøc nghiÖm cña ®a thøc Chebyshev xk ë trªn ta suy ra c«ng thøc cña ®a thøc Chebyshev trªn ®o¹n [a, b] b»ng phÐp ®æi biÕn 2x − a − ab t = , t ∈ [−1, 1]. b − a Tøc lµ 1 x = {(b − a)t + (a + b)}. 2 Khi ®ã víi mçi ®a thøc Pn(x), x ∈ [a, b] ta nhËn ®−îc (sau khi ®æi biÕn) ®a thøc 1 (b − a)n P (t) = P ( [(b − a)t + (a + b)]) = ( tn + ), n n 2 2n suy ra 2n 1 k P k≥ , n (b − a)n 2n−1 vËy (b − a)n k P k≥ . n 22n−1 Tõ ®ã, ta cã k Pn k= sup |Pn(x)| x∈[a,b] b − a a + b = sup |Pn( t + )| t∈[−1,1] 2 2 b (b − a) n = sup | n t + | t∈[−1,1] 2 (b − a)n (b − a)n (b − a)n = n sup |tn + | ≥ n n−1 = 2n−1 . 2 t∈[−1,1] 2 2 2 Nh− vËy víi mäi ®a thøc Pn x¸c ®Þnh trªn [a, b] th× (b − b)n kP k ≥ . n 2n Tn(t) Nh−ng theo kÕt qu¶ cña ®Þnh lý trªn th× ®a thøc 2n−1 lµ ®a thøc cã ®é lÖch nhá nhÊt trªn ®o¹n [−1, 1] nªn 2x−a−b n n Tn( ) (b − a) (b − a) k b−a k. = . 2n−1 2n 22n−1 2i+1 Gi¶ sö nghiÖm cña Tn(t) trªn [−1, 1] lµ θi = cos( n )π, i = 1, 2, , n suy ra 1 2i + 1 x = {(b − a) cos π + (a + b)}, i = 0, 1, , n. i 2 2(n + 1)
  30. Gi¶i tÝch sè 29 4. Chän mèc néi suy tèi −u Tõ c«ng thøc sai sè cña ph−¬ng ph¸p néi suy M Yn |f(x) − P (x)| ≤ | n+1 (x − x )|. n (n + 1)! i i=0 Qn Ta cã: ω(x) := i=0(x − xi), lµ ®a thøc cã bËc n + 1. Theo kÕt qu¶ võa nhËn ®−îc th× (b − a)n+1 k ω(x) k≥ . 22n+1 NÕu ta lÊy 2x−a−b n+1 Tn+1( ) (b − a) ω(x) = b−a . , 2n 2n + 1 th× 2x−a−b n+1 n+1 Tn+1( ) (b − a) (b − a) kω(x)k = k b−a k. = . 2n 2n+1 22n+1 Bëi vËy nÕu ta lÊy c¸c mèc néi suy chÝnh lµ c¸c nghiÖm xi, i = 0, 1, 2, , n th× sai sè |R(x)| = |f(x) − Pn(x)| M M (b − a)n+1 ≤ | n+1 Πn (x − x )| = n+1 . (n + 1)! i=0 i (n + 1)! 22n+1 VËy c¸c nghiÖm xi, i = 0, 1, 2, , n chÝnh lµ c¸c mèc néi suy tèi −u. KÕt luËn: §Ó cã mèc néi suy tèi −u th× c¸c mèc néi suy xi lµ 1 2i + 1 x = {(b − a) cos π + (a + b)}, i = 0, 1, , n. i 2 2(n + 1) Khi ®ã, sai sè cho bëi c«ng thøc M (b − a)n+1 |R(x)| ≤ . (n + 1)! 22n+1 VÝ dô: √ XÐt hµm f(x) = x + 1, T×m ®a thøc néi suy Q3 cña f trªn [0, 1] víi c¸c mèc néi suy tèi −u. Nh− vËy, theo kÕt qu¶ ë trªn ta cã 4 mèc néi suy tèi −u lµ: 1 2i + 1 x = {cos( π) + 1}, i = 0, 1, 2, 3. i 2 4
  31. Gi¶i tÝch sè 30 §a thøc néi suy (x − x1)(x − x2)(x − x3) √ (x − x0)(x − x2)(x − x3) Q3(x) = + x1 + 1 (x0 − x1)(x0 − x2)(x0 − x3) (x1 − x0)(x1 − x2)(x1 − x3) √ (x − x0)(x − x1)(x − x3) √ (x − x0)(x − x1)(x − x2) + x2 + 1 + + x3 + 1 . (x2 − x0)(x2 − x1)(x2 − x3) (x3 − x0)(x3 − x1)(x3 − x2) ¦íc l−îng tèt nhÊt cña phÐp néi suy trong tr−êng hîp nµy lµ: √ 1 | x + 1 − Q (x)| ≤ . 3 4!27
  32. Gi¶i tÝch sè 31 Ch−¬ng 4 TÝnh GÇn §óng §¹o Hµm Vµ TÝch Ph©n 4.1 Dïng néi suy Lagrange tÝnh gÇn ®óng ®¹o hµm Ta ph¶i tÝnh ®¹o hµm cña mét hµm d¹ng b¶ng hoÆc mét hµm ë d¹ng gi¶i tÝch phøc t¹p th× th«ng th−êng ta dïng ph−¬ng ph¸p tÝnh gÇn ®óng. Ch¼ng h¹n ta cã thÓ thay hµm f(x) b»ng ®a thøc néi suy nµo ®ã cña f(x) lµ P (x) víi phÇn d− R(x): f(x) = P (x) + R(x), f (n+1)(ξ) Yn R(x) = (x − x ), ξ = ξ(x) ∈ (x , x). (n + 1)! i 0 i=0 Khi ®ã f 0(x) = P 0(x) + R0(x). PhÇn nµy ta sö dông néi suy Lagrange ®Ó tÝnh ®¹o hµm. Thay gÇn ®óng f(x) b»ng ®a thøc néi suy Lagrange cÊp n lµ Qn, khi ®ã f(x) = Qn(x) + R(x). Trong ®ã Xn Qn(x) = ykPk(x), k=0 (x − x0)(x − x1) (x − xk−1)(x − xk+1) (x − xn) Pk(x) = . (xk − x0)(xk − x1) (xk − xk−1)(xk − xk+1) (xk − xn) Theo c«ng thøc sai sè cña phÐp néi suy Lagrange ta cã: f (n+1)(ξ) Yn R(x) = (x − x ), ξ = ξ(x) ∈ (x , x). (n + 1)! i 0 i=0 Suy ra d f (n+1)(ξ) Yn R0(x) = { (x − x )} dx (n + 1)! i i=0 f (n+1)(ξ) d Yn = . { (x − x )}. (n + 1)! dx i i=0 Tõ ®ã, ta cã f (n+1)(ξ) d Y R0(x ) = { (x − x )}. k (n + 1)! dx k i i6=k
  33. Gi¶i tÝch sè 32 VÝ dô trong tr−êng hîp sö dông néi suy Lagrange cÊp 1,Q1(x) ta cã: x − x1 x − x0 Q1(x) = y0 + y1 , x0 − x1 x1 − x0 f”(ξ) R(x) = (x − x )(x − x ). 2! 0 1 VËy 0 y1 − y0 0 f”(ξ) Q (x0) = ,R (x0) = (x1 − x0). x1 − x0 2! Khi ®ã cã c«ng thøc ®Ó tÝnh ®¹o hµm cña f lµ 0 f(x1) − f(x0) f”(ξ) f (x0) = − (x1 − x0). x1 − x0 2! DÔ thÊy r»ng ®©y l¹i lµ khai triÓn Taylor cña f t¹i x0 ®· biÕt. 4.2 TÝnh gÇn ®óng tÝch ph©n. Gi¶ sö cÇn tÝnh tÝch ph©n: Z b I := f(x)dx. a §Ó tÝnh gÇn ®óng tÝch ph©n I, th«ng th−êng ta thay hµm f(x) b»ng ®a thøc néi suy Q(x) råi lÊy tÝch ph©n ®a thøc néi suy nµy lµm gi¸ trÞ gÇn ®óng cña tÝch ph©n I, tøc lµ Z b Z b I := f(x)dx ' Q(x)dx. a a 4.2.1 Ph−¬ng ph¸p h×nh thang. Cho hµm f(x) x¸c ®Þnh trªn [a, b]. Chia ®o¹n [a, b] thµnh n ®o¹n con b»ng nhau bëi c¸c ®iÓm chia xi, víi i := 0, ··· , n sao cho: a = x0 < x1 < ··· < xn = b. b−a Khi ®ã xi = a + ih, h = n , i = 0, 1, , n. y 6 - a xi−1 xi b x
  34. Gi¶i tÝch sè 33 Thay diÖn tÝch h×nh thang cong b»ng diÖn tÝch h×nh thang trªn ®o¹n [xi−1, xi], ta cã Z xi y + y f(x)dx = i−1 i h. xi−1 2 T−¬ng tù víi c¸c ®o¹n cßn l¹i vµ lÊy tæng trªn tÊt c¶ ®o¹n con, ta cã: Z n−1 Z n−1 b X xi+1 X y + y f(x)dx = f(x)dx ' h. i i+1 . 2 a i=0 xi i=0 Cuèi cïng ta cã c«ng thøc h×nh thang sau: Z b b − a f(x)dx ' (y0 + 2y1 + + 2yn−1 + yn). a 2n C«ng thøc sai sè a. Sai sè ®Þa ph−¬ng: Do ta sö dông ®a thøc néi suy Lagrange Q1(x) ®Ó xÊp xØ f(x) trªn [xi−1, xi], i = 1, 2, , n. C«ng thøc cô thÓ : x − xi x − xi−1 f(x) = yi−1 + yi + R1(x), xi−1 − xi xi − xi−1 Z Z xi xi yi−1 − yi f(x)dx = .h + R1(x)dx. xi−1 2 xi−1 Trong ®ã f”(ξ) M |R (x)| = | (x − x )(x − x )| ≤ (x − x )(x − x) 1 2 i−1 i 2 i−1 i víi M = supx∈[a,b] |f”(x)|. Tõ ®ã cã Z Z xi xi yi−1 − yi | f(x)dx − .h| ≤ |R1(x)|dx xi−1 2 xi−1 Z M xi Mh3 ≤ (x − xi−1)(xi − x)dx = . 2 xi−1 12 b. Sai sè toµn phÇn: Sai sè toµn phÇn lµ sai sè trªn ®o¹n [a, b]. Ký hiÖu R lµ sai sè toµn phÇn, ta cã Mh3 M(b − a) R = n. = h2. 12 12 R 1 x2 VÝ dô: TÝnh tÝch ph©n I = 0 e dx b»ng ph−¬ng ph¸p h×nh thang víi n = 10. Ta cã: M := max {|y(2)(x)|} = max {|4(4x + 1)ex2 |} = 20.e. x∈[0,1] x∈[0,1]
  35. Gi¶i tÝch sè 34 C«ng thøc tÝnh nh− sau: Z 1 I = ex2 dx 0 1 2 2 2 2 2 2 2 2 2 ' {1+e+2(e(0,1) +e(0,2) +e(0,3) +e(0,4) +e(0,5) +e(0,6) +e(0,7) +e(0,8) +e(0,9) )}. 20 Trong ®ã sai sè toµn phÇn cho bëi: (b − a)Mh2 (0, 1)2.20.e |R| ≤ = . 12 12 4.2.2 Ph−¬ng ph¸p Parabol Cho hµm f(x) x¸c ®Þnh trªn [a, b]. Chia ®o¹n [a, b] thµnh 2n ®o¹n con b»ng nhau bëi c¸c ®iÓm chia xi, víi i := 0, ··· , 2n sao cho: a = x0 < x1 < ··· < x2n = b. b−a Khi ®ã xi = a + ih, h = 2n , i = 0, 1, , 2n. y 6 M2i M2i−1 M2i−2 - a x2i−2 x2i−1 x2i b x Trªn mçi ®o¹n [x2i−2, x2i], i = 1, 2, , n, ta thay f(x) b»ng ®a thøc néi suy bËc hai Q2(x) víi c¸c mèc néi suy x2i−2, x2i−1, x2i C«ng thøc cô thÓ : (x − x2i−1)(x − x2i) Q2(x) = y2i−2 (x2i−2 − x2i−1)(x2i−2 − x2i) (x − x2i−2)(x − x2i) +y2i−1 (x2i−1 − x2i−2)(x2i−1 − x2i) (x − x2i−2)(x − x2i−1) +y2i . (x2i − x2i−2)(x2i − x2i−1) Theo c«ng thøc néi suy f(x) = Q2(x) + R2(x).
  36. Gi¶i tÝch sè 35 Tõ ®ã Z Z Z x2i x2i x2i f(x)dx = Q2(x)dx + R2(x)dx. x2i−2 x2i−2 x2i−2 DÔ thÊy Z x2i h Q2(x)dx = (y2i−2 + 4y2i−1 + y2i). x2i−2 3 VËy Z Z x2i h x2i f(x)dx = (y2i−2 + 4y2i−1 + y2i) + R2(x)dx. x2i−2 3 x2i−2 T−¬ng tù víi c¸c ®o¹n cßn l¹i vµ lÊy tæng trªn tÊt c¶ ®o¹n con, ta cã: Z n Z n b X x2i X h f(x)dx = f(x)dx ' (y + 4y + y ). 3 2i−2 2i−1 2i a i=1 x2i−2 i=1 Cuèi cïng ta cã c«ng thøc ®Ó tÝnh tÝch ph©n nh− sau: Z b b − a f(x)dx ' (y0 + 4y1 + 2y2 + + 4y2n−1 + y2n). a 6n C«ng thøc sai sè a. Sai sè ®Þa ph−¬ng: §Æt Z xi+h h R = f(x)dx − [f(xi − h) + 4f(xi) + f(xi + h)]. xi−h 3 XÐt hµm Z xi+t t Φ(t) = f(x)dx − [f(xi − t) + 4f(xi) + f(xi + t)]. xi−t 3 §Æt t F (t) := Φ(t) − ( )5Φ(h), 0 ≤ t ≤ h. h DÓ thö l¹i r»ng F (0) = F (h) = 0; F 0(0) = F ”(0) = 0, t 60t2 F (3)(t) = − [f (3)(x + t) − f (3)(x − t)] − Φ(h). 3 i i h5 (3) Sö dông ®Þnh lý gi¸ trÞ trung b×nh cho f nªn tån t¹i ξ ∈ [xi + t, xi − t] sao cho (3) (3) (4) f (xi + t) − f (xi − t) = f (ξ)(xi + t − xi + t). Suy ra 2t2 90 F (3)(t) = − [f (4)(ξ) + Φ(h)]. 3 h5
  37. Gi¶i tÝch sè 36 Bëi F (0) = F (h) nªn tån t¹i t1 ∈ (0, h), 0 F (t1) = 0. 0 0 Bëi F (0) = F (t1) nªn tån t¹i t2 ∈ (0, t1), F ”(t2) = 0. Bëi F ”(0) = F ”(t2) nªn tån t¹i t3 ∈ (0, t2), (3) F (t3) = 0. Suy ra h5 Φ(h) = − f (4)(ξ), x − t ≤ x + t . 90 i 3 i 3 VËy Z xi+h 5 h h (4) f(x)dx = [f(xi − h) + 4f(xi) + f(xi + h)] − f (ξ). xi−h 3 90 (4) §Æt M := maxx∈[a,b] |f (x)|, ta nhËn ®−îc Mh5 |R| ≤ . 90 b. Sai sè toµn phÇn lµ (b − a) R ≤ Mh4. T p 180 R 1 x2 VÝ dô: TÝnh tÝch ph©n I = 0 e dx b»ng ph−¬ng ph¸p Parabol víi n = 5. Ta cã: M := max {|y(4)(x)|} = max {|4(4x4 + 12x3 + 3)ex2 |} = 76.e. x∈[0,1] x∈[0,1] C«ng thøc tÝnh nh− sau: Z 1 I = ex2 dx 0 1 2 2 2 2 2 2 2 2 2 ' {1+e+2(e(0,2) +e(0,4) +e(0,6) +e(0,8) )+4(e(0,1) +e(0,3) +e(0,5) +e(0,7) +e(0,9) )}. 30 Trong ®ã sai sè toµn phÇn cho bëi: (b − a)Mh4 (0, 1)4.76.e |R| ≤ = . 180 180
  38. Gi¶i tÝch sè 37 Ch−¬ng 5 Gi¶i Ph−¬ng Tr×nh Phi TuyÕn Ch−¬ng nµy tr×nh bµy mét sè ph−¬ng ph¸p gi¶i ph−¬ng tr×nh f(x) = 0 trong ®ã f : R → R. 5.1 Ph−¬ng ph¸p ®å thÞ §Çu tiªn ta t×m c¸ch ®−a ph−¬ng tr×nh f(x) = 0 vÒ d¹ng t−¬ng ®−¬ng g(x) = h(x), TiÕp theo vÏ ®å thÞ cña c¸c hµm y = g(x) vµ y = h(x) ®Ó t×m giao ®iÓm cña c¸c ®å thÞ nµy. Hßanh ®é giao ®iÓm chÝnh lµ nghiÖm ξ cÇn t×m. y 6 y = h(x) y = g(x) - 0 a ξ b x 5.2 Ph−¬ng ph¸p chia ®«i. Gi¶ sö f(x) liªn tôc trªn (a, b) vµ f(a).f(b) < 0 th× f(x) cã Ýt nhÊt mét nghiªm trªn (a, b). Ta dïng ph−¬ng ph¸p chia ®«i liªn tiÕp ®o¹n [a, b] ®Ó t×m gi¸ trÞ gÇn ®óng cña nghiÖm nh− sau. Kh«ng mÊt tæng qu¸t xem f(a) < 0 < f(b). Chia ®«i [a, b] bëi ®iÓm a + b c = . NÕu f(c) = 0, th× c = ξ. NÕu f(c) 6= 0, x¶y ra hai tr−êng hîp: 2 a. NÕu f(c)f(a) < 0, th× chän ®o¹n [a1, b1], a1 = a, b1 = c. b. NÕu f(c)f(b) < 0, th× chän ®o¹n [a1, b1], a1 = c, b1 = b. Khi ®ã f(a1) vµ f(b1) tr¸i dÊu. TiÕp tôc qu¸ tr×nh nªu trªn, cuèi cïng hoÆc cã c ®Ó b − a f(c) = 0, hoÆc ta x©y dùng ®−îc d∙y ®o¹n th¾t l¹i [a , b ], n ∈ N, mµ b − a = n n n n 2n tháa f(an) < 0 < f(bn). Theo nguyªn lý d∙y ®o¹n th¾t l¹i sÏ tån t¹i ξ, an < ξ <
  39. Gi¶i tÝch sè 38 b − a b , ∀n ∈ N. Ta chøng minh f(ξ) = 0. ThËt vËy. Do b − a = → 0, khi n → ∞, n n n 2n nªn cã lim an = lim bn = ξ. n→∞ n→∞ Bëi f liªn tôc suy ra, f(ξ) = lim f(an) ≤ 0 vµ f(ξ) = lim f(an) ≥ 0. VËy f(ξ) = 0. n→∞ n→∞ y 6 f(a) a1 = a a2 a3 a4 0 - b4 b1 = b x b2 b3 f(b) ThuËt tãan thùc hiÖn nh− sau: a+b B−íc 1. LÊy c = 2 . NÕu f(c) = 0. Ta cã c lµ nghiÖm vµ dõng thuËt to¸n. NÕu f(c).f(a) 0 th× a := c. B−íc 2. NÕu |b − a| < ε th× nghiÖm gÇn ®óng lµ c. NÕu kh«ng quay l¹i b−íc 1. VÝ dô: Dïng ph−¬ng ph¸p chia ®«i gi¶i gÇn ®óng f(x) = x4 + 2x3 − x − 1 trªn ®o¹n [0, 1] víi sè b−íc n = 5. Do f(0) = −1, f(1) = 1 nªn nghiÖm x∗ ∈ [0, 1]. Chia ®«i [0, 1], c1 = 0.5, f(0.5) = −1.19. Ta chän [a1, b1] = [0.5, 1]. TiÕp tôc chia ®«i ta cã: F (0.75) = −0.59, f(0.875) = 0.05, f(0.8125) = −0.304, f(0.8438) = −0.135, f(0.8594) = 0.043. VËy nghiÖm gÇn ®óng 1 x∗ ' (0.859 + 0.875) = 0.867. 2
  40. Gi¶i tÝch sè 39 5.3 Ph−¬ng ph¸p lÆp ®¬n. §Ó gi¶i ®−îc b»ng ph−¬ng ph¸p lÆp ta ®−a ph−¬ng tr×nh f(x) = 0 vÒ d¹ng x = Φ(x). 0 NÕu Φ(x) ∈ [a, b] , Φ (x) ≤ q 0, khi phÐp lÆp tháa c«ng thøc (1 − q) | x − x |< ² n+1 n q th× dõng vµ lÊy xn+1 lµ nghiÖm gÇn ®óng (c«ng thøc nµy lµ ®iÒu kiÖn dõng). ThËt vËy: D∙y {xn} lµ d∙y Cauchy v× víi mäi n, ∃cn ∈ [a, b] sao cho | xn+1 − xn |=| Φ(xn) − Φ(xn−1) | 0 =| Φ (cn) | × | xn+1 − xn |≤ q | xn+1 − xn | . Tõ ®ã, ta cã | xn+1 − xn |≤ q | xn − xn−1 |, | xn − xn−1 |≤ q | xn−1 − xn−2 |, | x2 − x1 |≤ q | x1 − x0 | . VËy n | xn+1 − xn |≤ q | x1 − x0 | . Víi mçi p ∈ N ta cã: | xn+p − xn | =| xn+p − xn+p−1 + xn+p−1 − + xn+1 − xn | n+p+1 n ≤ q | x1 − x0 | + + q | x1 − x0 | n 2 n−1 = q (1 + q + q + + q ) | x1 − x0 | . Tõ ®ã qn | x − x |≤ | x − x | . n+p n 1 − q 1 0 ∗ Bëi 0 ≤ q < 1 d∙y {xn} héi tô tíi x . Qua giíi h¹n ta cã lim xn = lim Φ(xn), n→∞ n→∞ suy ra x∗ = Φ(x∗).
  41. Gi¶i tÝch sè 40 Cho p → +∞ trong biÓu thøc qn | x − x |≤ | x − x | . n+p n 1 − q 1 0 Ta cã qn | x − x∗ |≤ | x − x | . n 1 − q 1 0 Cã nhiÒu c¸ch ®−a ph−¬ng tr×nh f(x) = 0 vÒ d¹ng gi¶i ®−îc b»ng ph−¬ng ph¸p lÆp ®¬n, ch¼ng h¹n xÐt hµm nµo ®ã µ(x) 6= 0, ∀x ∈ [a, b], ®Æt Φ(x) = x + µ(x)f(x). Hµm µ(x) ®−îc chän sao cho ∀x ∈ [a, b], | Φ0(x) 0 sao cho ∀x ∈ (x∗ − α, x∗ + α) ∝, | Φ0(x) |≤ q < 1. VÝ dô: Gi¶i ph−¬ng tr×nh f(x) = x3 + x − 1000 = 0 trªn [9, 10]. Cã nhiÒu c¸ch ®−a f(x) = 0 vÒ d¹ng x = φ(x). Cô thÓ ta dïng d¹ng: √ x = 3 1000 − x. Do 0 1 − 2 1 2 1 q := max |φ (x)| = max | (1000 − x) 3 | ≤ × (999) 3 ' . x∈[9,10] x∈[9,10] 3 3 300 XÊp xØ ban ®Çu x0 = 10, ta cã c«ng thøc lÆp: √ 3 xn+1 = 1000 − xn, n = 0, 1, 2, 3 √ √ 3 3 Víi n = 1 cã x1 = 990, n = 2 cã x2 = 1000 − x1 ' 9.96666. Víi n = 3 nghiÖm gÇn ®óng x3 ' 9.96667. Sai sè cho bëi 1 | x − x∗ |≤ × 0.0001. 3 300
  42. Gi¶i tÝch sè 41 5.4 Ph−¬ng ph¸p d©y cung 2 0 Gi¶ sö ph−¬ng tr×nh f(x) = 0 cã nghiÖm duy nhÊt trªn [a, b], f ∈ C[a,b], vµ f , f” kh«ng ®æi dÊu trªn [a, b]. §iÓm x ∈ [a, b] ®−îc gäi lµ ®iÓm Fourier, nÕu f(x)f”(x) > 0. a) Tr−êng hîp f 0 0, ∀x ∈ [a, b]. DÔ thÊy trong tr−êng hîp nµy a lµ ®iÓm Fourier v× f(a) > 0. Gäi xk lµ xÊp xØ thø k cña nghiÖm, x0 = b lµ xÊp xØ ban ®Çu y 6 M(a, f(a)) y = f(x) - 0 a ξx2 x1 b x N0(b, f(b)) N1(x1, f(x1)) Hoµnh ®é giao ®iÓm cña d©y cung MNk vµ trôc hoµnh trong ®ã M(a, f(a)) vµ Nk(xk, f(xk)) lµ xÊp xØ xk+1. Ph−¬ng tr×nh ®−êng th¼ng qua M vµ Nk nh− sau: f(x ) − f(a) y = f(a) + k (x − a). xk − a Cho y = 0 ta cã: f(xk)(xk − a) xk+1 = xk − . f(xk) − f(a) Suy ra f(xk) xk+1 − xk = − (xk − a). f(xk) − f(a) Cuèi cïng ta nhËn ®−îc c«ng thøc d©y cung f(xk) xk+1 = xk − (xk − a), k = 1, 2, , +∞. f(xk) − f(a) VËy trong tr−êng hîp nµy d∙y {xk} lµ d∙y ®¬n ®iÖu gi¶m héi tô tíi nghiÖm.
  43. Gi¶i tÝch sè 42 b) Tr−êng hîp f 0 > 0, f” > 0. Còng t−¬ng tù nh− tr−êng hîp a) ®∙ tr×nh bµy ë trªn nh−ng víi ®iÓm b lµ Fourier vµ xÊp xØ ban ®Çu lµ a ta cã c«ng thøc lÆp sau: f(xk)(xk − b) xk+1 = xk − . f(xk) − f(b) C«ng thøc sai sè 1. C«ng thøc sai sè thø nhÊt: Gi¶ sö |f 0(x)| ≥ m > 0, ∀x ∈ [a, b]. Khi ®ã cã ∗ |f(xk)| = |f(xk) − f(x )| 0 ∗ ∗ = |f (uk)(xk − x )| ≥ m|xk − x |. VËy ta cã c«ng thøc sai sè thø nhÊt: |f(x )| |x − x∗| ≤ k . k+1 m 2. C«ng thøc sai sè thø hai: Gi¶ sö ∀x ∈ [a, b], 0 < m ≤ |f 0(x)| ≤ M. Tõ c«ng thøc d©y cung ta cã: f(xk)(xk − a) xk+1 = xk − . f(xk) − f(a) Suy ra f(xk) − f(a) −f(xk) = (xk+1 − xk). xk − a ∗ ∗ XÐt vÕ tr¸i, do f(x ) = 0 vµ tõ c«ng thøc sè gia, tån t¹i uk ∈ (x , xk) sao cho ∗ ∗ 0 −f(xk) = f(x ) − f(xk) = (x − xk)f (uk). XÐt vÕ ph¶i, tõ c«ng thøc sè gia, tån t¹i x¯k ∈ (xk+1, xk) sao cho f(xk) − f(a) 0 .(xk+1 − xk) = f (x ¯k)(xk+1 − xk). xk − a VËy ∗ 0 0 (x − xk)f (uk) = f (x ¯k)(xk+1 − xk). Tõ ®ã ∗ 0 0 (x − xk+1 + xk+1 − xk)f (uk) = f (x ¯k)(xk+1 − xk).
  44. Gi¶i tÝch sè 43 Hay 0 0 ∗ |f (x ¯k) − f (uk)| |x − xk+1| = 0 .|xk+1 − xk|. |f (uk)| H¬n n÷a do 0 0 |f (x ¯k − f (uk)| ≤ M − m, suy ra cã c«ng thøc sai sè thø 2, M − m |x − x∗| ≤ |x − x |. k+1 m k+1 k VÝ dô: Gi¶i ph−¬ng tr×nh f(x) = x3 − 0.02x2 − 0.2x − 1.2 = 0 trªn [0, 1.5] víi ² = 0.002. DÔ thÊy ®iÓm Fourier lµ b = 1.5 vµ m = 3.49. §Æt 3 2 fn = xn − 0.2xn − 0.2 − 1.2 ta cã fn xn+1 = xn − (1.5 − xn). 1.425 − fn Bëi x3 = 1.198, f(x3) ' −0.0072. Sai sè cho bëi 0.0072 | x − x∗ | 0, ®iÓm nµy ®−îc gäi lµ ®iÓm Fourier. Ph−¬ng tr×nh tiÕp tuyÕn víi ®−êng cong y = f(x) t¹i ®iÓm M0(x0, f(x0)) cã d¹ng 0 y = f (x0)(x − x0) + f(x0). TiÕp tuyÕn c¾t trôc hßanh t¹i ®iÓm x1, 0 0 = f (x0)(x1 − x0) + f(x0). Tõ ®ã, ta cã f(x0) x1 = x0 − 0 . f (x0) Víi vai trß x0 lµ xn ta cã d¹ng tæng qu¸t f(xn) xn+1 = xn − 0 , n = 1, 2, , +∞. f (xn)
  45. Gi¶i tÝch sè 44 D·y lÆp nµy ta gäi lµ d·y lÆp Newton. §Þnh lý 5.5.1 Víi c¸c gi¶ thiÕt trªn, d·y lÆp Newton héi tô tíi nghiÖm cña ph­¬ng tr×nh f(x) = 0. Chøng minh: Kh«ng gi¶m tæng qu¸t coi f” > 0, f 0 x th× do f < 0 nªn ∗ f(xn) < f(x ) = 0. M©u thuÉn víi f(xn) ≥ 0. Tõ ®ã d·y {xn} cã giíi h¹n lµ θ. Ký hiÖu M := sup {|f 0(x)|}. x∈[a,b] Ta cã 0 |f(xn)| = |f (xn)|.|xn+1 − xn| ≤ M|xn+1 − xn|.
  46. Gi¶i tÝch sè 45 §Ó m« t¶ vÒ mÆt h×nh häc cña thuËt to¸n nªu trong chøng minh cña ®Þnh lý trªn, ta xem h×nh sau: 6 M(b, f(b)) y N1(x1, f(x1)) ∗ x - 0 ax2 x1 b x y = f(x) C«ng thøc sai sè N(a, f(a)) 0 Gi¶ sö |f”(x)| ≤ M1 vµ |f (x)| ≥ M2 víi mäi x ∈ [a, b]. Mét mÆt ta cã ∗ 0 ∗ f(xn+1) = f(xn+1) − f(x ) = f (¯xn+1)(xn+1) − x ). Suy ra ∗ f(xn+1) 2 |xn+1 − x | ≤ |xn+1 − xn| . M2 MÆt kh¸c tõ c«ng thøc Taylor, ta cã f”(ξ ) f(x ) = f(x ) + f 0(x )(x − x ) + n (x − x )2 n+1 n n n+1 n 2 n+1 n f”(ξ ) = n (x − x )2. 2 n+1 n Tõ ®ã, suy ra M |f(x )| ≤ 1 |x − x |2. n+1 2 n+1 n VËy ta cã c«ng thøc sai sè ∗ M1 2 |xn+1 − x | ≤ |xn+1 − xn| . 2M2 Tèc ®é héi tô nhanh h¬n ph−¬ng ph¸p d©y cung, lËp tr×nh t−¬ng ®èi ®¬n gi¶n. tg(x) 3.π VÝ dô: Dïng ph−¬ng ph¸p tiÕp tuyÕn gi¶i ph−¬ng tr×nh x − 1 = 0 trªn (π, 2 ) sai sè ² = 0.0001.
  47. Gi¶i tÝch sè 46 ViÕt l¹i ph−¬ng tr×nh trªn nh− sau: f(x) = sin(x) − x sin(x) = 0. 0 3.π DÔ thÊy f (x) < 0, f”(x) < 0, ∀x ∈ (π, 2 ). Dïng c«ng thøc f(xn) xn+1 = xn − 0 , n = 0, 1, 2, f (xn) 3.π LÊy x0 = 2 , ta nhËn ®−îc x1 = 9, x2 = 4.50004, x3 = 4.49343. Sai sè cho bëi c«ng thøc: 3.π |x − x∗| ≤ |x − x |2 3 4 3 2 3.π = |4.49343 − 4.50005|2 4 3.π = |0.00662|2 ' 0.0001. 4 5.6 Gi¶i ®a thøc PhÇn nµy xÐt ph−¬ng ph¸p gi¶i ph−¬ng tr×nh f(x) = 0 víi f(x) lµ mét ®a thøc bËc n Pn i nµo ®ã. Gi¶ sö f(x) = i=0 aix ta cã thÓ viÕt l¹i nã ë d¹ng Horner f(x) = a0 + x(a1 + + x(an−1 + xan)) ). §Æt bn−1 = an bn−2 = an−1 + xbn−1 bi−1 = ai + xbi b0 = a1 + xb1 f(x) = a0 + xb0. §Ó tÝnh gi¸ trÞ cña ®a thøc mµ ta dïng c¸ch ®Æt ë trªn, ta gäi lµ ph−¬ng ph¸p Horner. TÝnh to¸n ®−îc thùc hiÖn theo s¬ ®å sau: Gi¶ sö cÇn chia ®a thøc f(x) cho (x − x0). Ta viÕt nh− sau f(x) = (x − x0)Qn−1(x) + f(x0). Trong ®ã n−1 Qn−1(x) = β0 + β1x + + βn−1x .
  48. Gi¶i tÝch sè 47 Tõ ®ã cã n n−1 f(x) = βn−1x + (βn−2 − x0βn−1)x + + (β0 − x0β1)x + f(x0) − x0β0. So s¸nh c¸c hÖ sè, ta cã an = βn−1, an−1 = βn−2 − x0βn−1, a1 = β0 − x0β1, a0 = f(x0) − x0β0. So s¸nh víi ph−¬ng ph¸p Horner ®· tr×nh bµy ë trªn víi f(x0) ta suy ra bi = βi, ∀i := 0, 1 n. Sö dông liªn tiÕp ph−¬ng ph¸p, ta cã f(x) = (x − x0)Qn−1(x) + R0(x0), Qn−1(x) = (x − x0)Qn−2(x) + R1(x0), Q1(x) = (x − x0)Q0(x) + Rn−1(x0), Q0(x) = Rn(x). VËy n f(x) = R0(x0) + R1(x0)(x − x0) + + Rn(x0)(x − x0) . Theo c«ng thøc Taylor th× Xn f (i)(x ) f(x) = 0 (x − x )i. i! 0 i=0 So s¸nh hai biÓu thøc cïng cña f(x) suy ra: (i) f (x0) = i!Ri(x0), i := 0, 1, , n. trong ®ã Ri(x0) ®−îc tÝnh tõ ph−¬ng ph¸p Horner. 5.7 Gi¶i hÖ hai ph−¬ng tr×nh phi tuyÕn b»ng ph−¬ng ph¸p lÆp ®¬n XÐt hai ph−¬ng tr×nh víi hai Èn: ½ F1(x, y) = 0, F2(x, y) = 0. Gi¶ sö hÖ cã nghiÖm c« lËp. §Ó sö dông ph−¬ng ph¸p lÆp ta ®−a hÖ trªn vÒ d¹ng: ½ x = Φ1(x, y), y = Φ2(x, y).
  49. Gi¶i tÝch sè 48 ThuËt to¸n thùc hiÖn nh− sau: ½ xn+1 = Φ1(xn, yn), yn+1 = Φ2(xn, yn). Trong ®ã (x0, y0) lµ gi¸ trÞ ban ®Çu. Gi¶ sö hÖ chØ cã nghiÖm duy nhÊt (x∗, y∗) trong U = [a, b] × [a, b] ⊂ R2. C¸c hµm Φ1(x, y), Φ2(x, y) kh¶ vi liªn tôc trong U. ∂Φ ∂Φ | 1 | + | 2 | ≤ q < 1, ∂x ∂y 1 ∂Φ ∂Φ | 1 | + | 2 | ≤ q < 1. ∂x ∂y 2 HoÆc ∂Φ ∂Φ | 1 | + | 1 | ≤ q < 1, ∂x ∂y 1 ∂Φ ∂Φ | 2 | + | 2 | ≤ q < 1. ∂x ∂y 2 C¸c gi¸ trÞ (xn, yn) ∈ U, ∀n = 0, 1, 2, , +∞, th× d·y ®iÓm xÊp xØ (xn, yn) x¸c ®Þnh trªn héi tô tíi nghiÖm (x∗, y∗) cña hÖ. Sai sè cho bëi: ∗ ∗ max{q1, q2} |xn − x | + |yn − y | ≤ (|xn − xn−1| + |yn − yn−1)|. 1 − max{q1, q2}
  50. Gi¶i tÝch sè 49 Ch−¬ng 6 Gi¶i HÖ Ph−¬ng Tr×nh §¹i Sè TuyÕn TÝnh 6.1 Mét vµi kh¸i niÖm cÇn thiÕt XÐt hÖ ph−¬ng tr×nh ®¹i sè tuyÕn tÝnh   a x + a x + + a x = b ,  11 1 12 2 1n n 1 a21x1 + a22x2 + + a2nxn = b2,   an1x1 + an2x2 + + annxn = bn. Ma trËn hÖ sè cña hÖ   a11 a12 a1n  a a a  A :=  21 22 2n    an1 a12 ann ViÕt d−íi d¹ng to¸n tö tuyÕn tÝnh Ax = b. Trong ®ã > n n b = (b1, b2, , bn) ∈ R x = (x1, x2, , xn) ∈ R . 6.2 Ph−¬ng ph¸p Gauss 6.2.1 Ph−¬ng ph¸p Gauss gi¶i hÖ ®¹i sè tuyÕn tÝnh §Ó thuËn tiÖn cho thuËt to¸n ta xÐt hÖ ®¹i sè tuyÕn tÝnh trªn víi c¸ch ®Æt (c¸c sè h¹ng tù do) ai,n+1 := bi. Khi ®ã hÖ ®¹i sè tuyÕn tÝnh trë thµnh   a x + a x + + a x = a ,  11 1 12 2 1n n 1,n+1 a21x1 + a22x2 + + a2nxn = a2,n+1,   an1x1 + an2x2 + + annxn = an,n+1. Ph−¬ng ph¸p ®−îc chia thµnh hai b−íc
  51. Gi¶i tÝch sè 50 a. B−íc thuËn: Dïng phÐp biÕn ®æi t−¬ng ®−¬ng ®−a hÖ vÒ d¹ng tam gi¸c trªn (D∗) sau:   x + b(0)x + b(0)x + + b(0) x + b(0) x = b(0)  1 12 2 13 3 1,n−1 n−1 1,n n 1,n+1  (1) (1) (1) (0)  0.x1 + x2 + b23 x3 + + b2,n−1xn−1 + b2n xn = b2,n+1  (n−2) (n−2)  0.x1 + 0.x2 + 0.x3 + + xn−1 + bn−1,nxn = bn−1,n+1  (n−1) 0.x1 + 0.x2 + 0.x3 + + 0.xn−1 + xn = bn,n+1 Ph−¬ng ph¸p cô thÓ nh− sau: Gi¶ sö a11 6= 0 ta chia ph−¬ng tr×nh ®Çu cho phÇn tö dÉn a11 cã: (0) (0) (0) (0) (0) x1 + b12 x2 + b13 x3 + + b1,n−1xn−1 + b1,nxn = b1,n+1. Víi (0) a1j b1j = . a11 §Ó khö x1 trong c¸c ph−¬ng tr×nh cßn l¹i ta lÇn l−ît nh©n ph−¬ng tr×nh trªn cho a21, a31, , an1 vµ lÊy c¸c ph−¬ng tr×nh thø i, i = 2, 3, , n trõ t−¬ng øng cho c¸c ph−¬ng tr×nh võa nhËn ®−îc. KÕt qu¶ ta nhËn ®−îc hÖ míi:   a11x1 + a12x2 + + a1nxn = a1,n+1,  (1) (1) (1) 0x1 + a22 x2 + + a2n xn = a2,n+1,   (1) (1) (1) 0x1 + an2 x2 + + ann xn = an,n+1. Trong ®ã (1) (0) aij = aij − aikbkj , i = 2, 3, , n, j = 2, 3, , n. (1) TiÕp tôc ta chia ph−¬ng tr×nh thø hai cho phÇn tö dÉn a22 cã (1) (1) (1) x2 + b23 x3 + + b1n xn = b2,n+1. Víi (1) (1) a2j b2j = (1) , j = 3, 4, , n. a22 T−¬ng tù nh− trªn cho tíi khi nhËn ®−îc hÖ tam gi¸c trªn (T ∗) sau:   a11x1 + a12x2 + + a1nxn = a1,n+1,  (1) (1) (1) 0x1 + a22 x2 + + a2n xn = a2,n+1,   (n−1) (n−1) 0x1 + 0.x2 + + ann xn = an,n+1.
  52. Gi¶i tÝch sè 51 (i−1) Chia ph−¬ng tr×nh thø i trong hÖ nµy cho phÇn tö dÉn t−¬ng øng aii , i = 1, 2, , n ta nhËn ®−îc hÖ cã d¹ng tam gi¸c trªn (D∗). b. B−íc ng−îc: Dïng phÐp thÕ liªn tiÕp b¾t ®Çu tõ ph−¬ng tr×nh cuèi cïng trë lªn ®Ó x¸c ®Þnh nghiÖm xn, xn−1, , x2, x1. C«ng thøc tÝnh nh− sau: (k) (k−1) (k−1) (k−1) aij = aij − aik bkj , i, j = k, k + 1, , n, (k−1) (k−1) akj bkj = (k−1) , j = k + 1, , n. akk (k−1) Ph−¬ng ph¸p trªn thùc hiÖn ®−îc nÕu akk 6= 0. NÕu kh«ng th× b»ng c¸ch chuyÓn dßng (cét) t−¬ng øng ®Ó cã ®−îc tr−êng hîp trªn. VÝ dô: Ph−¬ng ph¸p ®−îc tr×nh bµy cô thÓ (cho hÖ 4 ph−¬ng tr×nh 4 Èn) nh− sau   a x + a x + a x + a x = a ,  11 1 12 2 13 3 14 4 15 a21x1 + a22x2 + a23x3 + a24x4 = a25,  a x + a x + a x + a x = a ,  31 1 32 2 33 3 34 4 35 a41x1 + a42x2 + a43x3 + a44x4 = a45. a. B−íc thuËn: Gi¶ sö a11 6= 0, ta chia ph−¬ng tr×nh thø nhÊt cho phÇn tö dÉn a11 thu ®−îc: (0) (0) (0) (0) x1 + b12 x2 + b13 x3 + b14 x4 = b15 víi b(0) = a1j . 1j a11 §Ó khö x1 trong ba ph−¬ng tr×nh cßn l¹i ta lÇn l−ît nh©n ph−¬ng tr×nh trªn cho a21, a31, a41 vµ lÊy c¸c ph−¬ng tr×nh thø i, i = 2, 3, 4 trõ t−¬ng øng cho c¸c ph−¬ng tr×nh võa nhËn ®−îc. KÕt qu¶ ta nhËn ®−îc hÖ míi:  (1) (1) (1) (1)  a22 x2 + a23 x3 + a24 x4 = a25 , (1) (1) (1) (1) a32 x2 + a33 x3 + a34 x4 = a35  (1) (1) (1) (1) a42 x2 + a43 x3 + a44 x4 = a45 . Trong ®ã (1) (0) aij = aij − aikbkj , i = 2, 3, 4, j = 2, 3, 4, 5. (1) TiÕp tôc ta chia ph−¬ng tr×nh thø nhÊt cho phÇn tö dÉn a22 cã (1) (1) (1) x2 + b23 x3 + b14 x4 = b25 .
  53. Gi¶i tÝch sè 52 Víi (1) (1) a2j b2j = (1) , j = 3, 4, 5. a22 T−¬ng tù c¸ch trªn ta khö x2 trong hÖ ta nhËn ®−îc hÖ ( (2) (2) (2) a33 x3 + a34 x4 = a35 , (2) (2) (2) a43 x3 + a44 x4 = a45 , víi (2) (1) (1) (1) aij = aij − ai2 b2j , i = 3, 4, j = 3, 4, 5. (2) Chia ph−¬ng tr×nh ®Çu cña hÖ cho a33 ®−îc (3) (3) a44 x4 = a45 . Trong ®ã (3) (2) (2) (2) aij = aij − ai3 b3j , i = 4, j = 4, 5. (3) Chia ph−¬ng tr×nh nhËn ®−îc cho a44 cã (3) a45 (3) x4 = (3) = b45 . a44 GÐp c¸c ph−¬ng tr×nh nhËn ®−îc, ta ®−îc hÖ  (0) (0) (0) (0)  x1 + b12 x2 + b13 x3 + b14 x4 = b15 ,  (1) (1) (1) 0.x1 + x2 + b23 x3 + b24 x4 = b25 , (2) (2)  0.x1 + 0.x2 + x3 + b34 x4 = b35 ,  (3) 0.x1 + 0.x2 + 0.x3 + x4 = b45 . B−íc thuËn kÕt thóc. b. B−íc ng−îc: Tõ ph−¬ng tr×nh cuèi cïng, ta cã (3) x4 = b45 . ThÕ x4 vµo ph−¬ng tr×nh thø ba ®−îc (2) (2) x3 = b35 − b34 x4. ThÕ x3, x4 vµo ph−¬ng tr×nh thø hai cã: (1) (1) (1) x2 = b25 − b24 x4 − b23 x3.
  54. Gi¶i tÝch sè 53 ThÕ x2, x3, x4 vµo ph−¬ng tr×nh cßn l¹i ta nhËn ®−îc nghiÖm (0) (0) (0) (0) x1 = b15 − b14 x4 − b13 x3 − b12 x2. §Õn ®©y kÕt thóc b−íc nghÞch vµ t×m ®−îc tÊt c¶ c¸c nghiÖm cña hÖ. ThuËt to¸n kÕt thóc. 6.2.2 Dïng ph−¬ng ph¸p Gauss tÝnh ®Þnh thøc §Ó tÝnh ®Þnh thøc cña ma trËn A ta thùc hiÖn chØ b−íc thuËn t−¬ng tù nh− khi gi¶i hÖ ®¹i sè tuyÕn tÝnh víi vÕ ph¶i lµ 0 cho tíi khi nhËn ®−îc hÖ tam gi¸c trªn (T ∗),   a11x1 + a12x2 + + a1nxn = 0,  (1) (1) 0x1 + a22 x2 + + a2n xn = 0,   (n−1) 0x1 + 0.x2 + + ann xn = 0. Ma trËn hÖ sè:   a11 a12 a1n  0 a(1) a(1)  T ∗ =  22 2n    (n−1) 0 0 ann ∗ (i−1) B©y giê ta chia dßng (i) cña ma trËn T cho phÇn tö dÉn aii sÏ nhËn ®−îc ma trËn  (0) (0) (0)  1 b12 b13 b1n  (1) (1)  B :=  0 1 b22 b2n    0 0 0 1 DÔ thÊy det B = 1. VËy (0) (1) (n−1) det A = a11 .a22 ann . 6.2.3 T×m ma trËn nghÞch ®¶o b»ng ph−¬ng ph¸p Gauss §Ó t×m ma trËn nghÞch ®¶o A = (xij)n cña ma trËn kh«ng suy biÕn A = (aij)n b»ng ph−¬ng ph¸p Gauss ta gi¶i n hÖ ph−¬ng tr×nh tuyÕn tÝnh cã cïng ma trËn hÖ sè A tøc lµ Xn aikxkj = δij, i, j = 1, 2, , n. k=1 Trong ®ã ½ 0, if i 6= j, δ = ij 1, if i = j.
  55. Gi¶i tÝch sè 54 6.3 Ph−¬ng ph¸p c¨n sè (ph−¬ng ph¸p Cholesky) XÐt hÖ ph−¬ng tr×nh tuyÕn tÝnh víi ma trËn hÖ sè lµ ma trËn ®èi xøng tøc lµ aij = aji, ∀i, j = 1, 2, , n. Ta biÓu diÔn ma trËn A thµnh tÝch hai ma trËn: A = ST S, T trong ®ã S = (sij lµ ma trËn tam gi¸c trªn tøc lµ (sij = 0, ∀i > j vµ S lµ ma trËn chuyÓn vÞ cña ma trËn S. §Ó ph©n tÝch ma trËn A thµnh tÝch cña ST S, ta sö dông c«ng thøc nh©n hai ma trËn: Xn aij = sikskj, i ≤ j. k=1 Hay i−1 X 1 2 2 s11 = (aii − ski) , i = 2, 3, , n, ; k=1 Pi−1 aij − k=1 skiskj sij = , ∀i j. NÕu sii 6= 0, ∀i = 1, 2, , n, th× detA = s11.s22 snn 6= 0 khi ®ã hÖ cã nghiÖm duy nhÊt. Cô thÓ ta t×m ®−îc:   s11 s12 s1n  0 s s  S :=  22 2n    0 0 tnn B©y giê ®Ó gi¶i Ax = b ta viÕt ST S = b. §Æt Sx = y ®−îc ST y = b. §Çu tiªn, ta gi¶i hÖ tam gi¸c d−íi ST y = b, ®Ó x¸c ®Þnh y. Sau khi gi¶i hÖ nµy, ta nhËn ®−îc nghiÖm b1 y1 = ; s11
  56. Gi¶i tÝch sè 55 Pi−1 bi − k=1 skiyk yi = , ∀i > 1. sii Sau ®ã gi¶i hÖ Sx = y ®Ó t×m nghiÖm x, cô thÓ nghiÖm sÏ ®−îc tÝnh nh− sau: yn xn = ; snn Pn yi − k=i+1 sikxk xi = , ∀i < n. sii 6.4 Ph−¬ng ph¸p lÆp ®¬n gi¶i hÖ ®¹i sè tuyÕn tÝnh Trong kh«ng gian Rn, xÐt c¸c chuÈn sau: kxk∞ = max |xi| : 1≤i≤n Xn kxk1 = |xi| : i=1 v u uXn t 2 kxk2 = xi . i=1 Khi ®ã ta cã c¸c chuÈn t−¬ng thÝch cña ma trËn A lµ Xn kAk∞ = max |ai,j| : 1≤i≤n j=1 Xn kAk1 = max |ai,j| : 1≤j≤n i=1 q T kAk2 = max λi(A A), 1≤i≤n T T trong ®ã λi(A A) lµ c¸c gi¸ trÞ riªng cña ma trËn A A. §Ó gi¶i b»ng ph−¬ng ph¸p lÆp ®¬n ®Çu tiªn ta ®−a ph−¬ng tr×nh Ax = b vÒ d¹ng x = Bx + g. Tõ nguyªn lý ¸nh x¹ co ta cã kÕt qu¶ sau: NÕu kBk < 1 th× d∙y lÆp: xk+1 = Bxk + g, k = 1, 2, , +∞,
  57. Gi¶i tÝch sè 56 n ∗ trong ®ã x0 ∈ R chän bÊt k× lµ héi tô tíi nghiÖm x duy nhÊt. Sai sè ®−îc cho bëi: kBkk kx − x∗k ≤ kx − x k, k 1 − kBk 1 0 kBk kx − x∗k ≤ kx − x k. k 1 − kBk k k−1 6.5 Ph−¬ng ph¸p Jacobi Ma trËn A = (aij)n gäi lµ cã ®−êng chÐo tréi nÕu mét trong hai ®iÒu kiÖn sau tháa X c1. |aij| < |aii|, ∀i = 1, 2, , n, j6=i X c2. |aij| < |ajj|, ∀j = 1, 2, , n. i6=j §Þnh lý NÕu A cã ®−êng chÐo tréi th× cã thÓ ®−a ph−¬ng tr×nh Ax = b vÒ d¹ng x = Bx + g víi ma trËn B cã chuÈn nhá h¬n 1. Chøng minh: XÐt tr−êng hîp c1, tõ   a x + a x + + a x = b ,  11 1 12 2 1n n 1 a21x1 + a22x2 + + a2nxn = b2,   an1x1 + an2x2 + + annxn = bn, ta chia ph−¬ng tr×nh thø i cho aii vµ chuyÓn c¸c sè h¹ng j 6= i sang vÕ ph¶i ta ®−îc a11 a12 a1n bi xi = − x1 − x2 − − xn + . aii aii aii aii Ph−¬ng tr×nh ®∙ cho t−¬ng ®−¬ng víi ph−¬ng tr×nh  a12 a1n b1 x1 = 0.x1 − x2 − − xn + ,  a11 a11 aii  a21 a2n b2 x2 = − x1 + 0.x2 − − xn + , a22 a22 a22   x = − an1 x − an2 x − + 0.x + bn . n ann 1 ann 2 n ann §Æt ma trËn B = (bij)n víi ½ 0, j = i, b = a ij − ij , j 6= i aii vµ bi gi = . aii
  58. Gi¶i tÝch sè 57 Khi ®ã ph−¬ng tr×nh cã d¹ng x = Bx + g. H¬n n÷a Xn kBk∞ = max |bij| < 1. 1≤i≤n i=1 Tr−êng hîp c2: Tõ   a x + a x + + a x = b ,  11 1 12 2 1n n 1 a21x1 + a22x2 + + a2nxn = b2,   an1x1 + an2x2 + + annxn = bn. §Æt: zi = aiixi vµ thay vµo ph−¬ng tr×nh vµ chuyÓn vÕ, ta cã  a12 a1n z1 = 0.z1 − z2 − − zn + b1,  a22 ann  a21 a2n z2 = − x1 + 0.z2 − − xn + bn, a11 ann   an1 an2 zn = − x1 − x2 − + 0.xn + bn. a11 a22 §Æt ma trËn B = (b ) víi ij n ½ 0, j = i, b = aij ij − , j 6= i, ajj vµ gi = bi. Khi ®ã ph−¬ng tr×nh cã d¹ng x = Bx + g. H¬n n÷a Xn kBk1 = max |bij| < 1. 1≤j≤n i=1 VÝ dô: Dïng ph−¬ng ph¸p lÆp ®¬n gi¶i hÖ ph−¬ng tr×nh   10x1 + 2x2 + x3 = 10, x + 10x + 2x = 12,  1 2 3 x1 + x2 + 10x3 = 8. Ma trËn hÖ sè   10 2 1 A :=  1 10 2  1 1 10 DÔ thÊy A lµ ma trËn ®−êng chÐo tréi.   x1 = 0x1 − 0.2x2 − 0.1x3 + 1, x = −0.1x + 0x − 0.2x + 1.2,  2 1 2 3 x3 = −0.1x1 − 0.1x2 + 0x3 + 0.8.
  59. Gi¶i tÝch sè 58 ViÕt l¹i ë d¹ng x = Bx + g, trong ®ã   0 − 0.2 − 0.1 B :=  −0.1 0 − 0.2  −0.1 − 0.1 0 vµ   1 g =  1.2  0.8 DÔ kiÓm l¹i X3 kBk∞ = max |bij| = max{0.3, 0.3, 0.2} = 0.3 < 1. 1≤i≤3 j=1 Dïng ph−¬ng ph¸p Jacobi, ta cã d·y lÆp x¸c ®Þnh bëi  (n+1) (n) (n) (n)  x1 = 0x1 − 0.2x2 − 0.1x3 + 1, (n+1) (n) (n) (n) x2 = −0.1x1 + 0x2 − 0.2x3 + 1.2,  (n+1) (n) (n) (n) x3 = −0.1x1 − 0.1x2 + 0x3 + 0.8, trong ®ã n = 0, 1, 2, , +∞ vµ xÊp xØ ban ®Çu   1 x(0) =  1.2  0.8 Víi n = 1,  (1)  x1 = 0 × 1 − 0.2 × 1.2 − 0.1 × 0.8 + 1 = 0.68, (1) x2 = −0.1 × 1 + 0 × 1.2 − 0.2 × 0.8 + 1.2 = 0.94,  (1) x3 = −0.1 × 1 − 0.1 × 1.2 + 0 × 0.8 + 0.8 = 0.58. Víi n = 2,  (2)  x1 = 0 × 0.68 − 0.2 × 0.94 − 0.1 × 0.58 + 1, (2) x2 = −0.1 × 0.68 + 0 × 0.94 − 0.2 × 0.58 + 1.2,  (2) x3 = −0.1 × 0.68 − 0.1 × 0.94.2 + 0 × 0.58 + 0.8. Sai sè cho bëi c«ng thøc kBkk (0.3)2 kx(2) − x∗k ≤ kx − x k = × (0.22). 1 − kBk 1 0 0.7
  60. Gi¶i tÝch sè 59 6.6 Ph−¬ng ph¸p Seidel Tõ ph−¬ng tr×nh x = Bx + g, ta ph©n tÝch ma trËn B thµnh tæng cña hai ma trËn tam gi¸c trªn vµ d−íi. Tøc lµ B = B1 + B2 trong ®ã   0 0 0  b 0 0  B :=  21  1   bn1 bn2 0 vµ   b11 b12 b1n  0 b b  B :=  22 2n  2   0 0 bnn Ph−¬ng tr×nh viÕt l¹i x = B1x + B2x + g. PhÐp lÆp x¸c ®Þnh nh− sau: (k+1) (k+1) (k) x = B1x + B2x + g, k := 1, 2, , +∞ Cô thÓ c«ng thøc lÆp x¸c ®Þnh theo Xi−1 Xn (k+1) (k+1) (k) xi = bijxj + bijxj + gi. j=1 j=i (k+1) C¸c thµnh phÇn xj võa tÝnh ®−îc víi j = 1, 2 , i − 1 sö dông ngay vµo ®Ó tÝnh thµnh (k+1) phÇn xi . §Þnh lý 6.6.1 NÕu kBk∞ < 1 th× ph−¬ng ph¸p Seidel héi tô. Chøng minh: DÔ thÊy tõ nguyªn lý ®iÓm bÊt ®éng th× ph−¬ng tr×nh trªn cã nghiÖm duy nhÊt x∗. §Ó xÐt sù héi tô cña d∙y lÆp theo ph−¬ng ph¸p Seidel ta xÐt Xi−1 Xn (k+1) ∗ (k+1) (k) ∗ xi − xi = bijxj + bijxj + gi − xi j=1 j=i
  61. Gi¶i tÝch sè 60 Xi−1 Xn Xi−1 Xn (k+1) (k) ∗ ∗ = bijxj + bijxj + gi − ( bijx + bijx + gi) j=1 j=i j=1 j=i Xi−1 Xn (k+1) ∗ (k) ∗ = bij(xj − x ) + bij(xj − x ). j=1 j=i Tõ ®ã, ta cã (k+1) ∗ |xi − xi | Xi−1 Xn (k+1) ∗ (k) ∗ ≤ |bij|.kxj − x k∞ + |bij|.kxj − x k∞. j=1 j=i Pi−1 Pn §Æt βi := j=1 |bij|; γi := j=i |bij| th× (k+1) ∗ (k+1) ∗ (k) ∗ |xi − xi | ≤ βikx − x k∞ + γikx − x k∞, ∀i. §Æt (k+1) ∗ (k+1) ∗ max |xi − xi | = |xi − xi | 1≤i≤n 0 0 (k+1) ∗ = kx − x k∞. Víi i = i0 ta nhËn ®−îc (k+1) ∗ (k+1) ∗ kx − x k∞ = |xi0 − xi0 | (k+1) ∗ (k) ∗ ≤ βi0 kx − x k∞ + γi0 kx − x k∞, VËy (k+1) ∗ γi0 (k) ∗ kx − x k∞ ≤ kx − x k∞ 1 − βi0 γi (k) ∗ ≤ max kx − x k∞. 1≤i≤n 1 − βi Bëi Xn Xn βi + γi = |bij| ≤ max |bij| = kBk∞ < 1, 1≤i≤n j=1 j=1 suy ra γi βi(1 − βi − γi) βi + γi − = ≥ 0, 1 − βi 1 − βi Do ®ã γi max ≤ max (βi + γi) = kBk∞ < 1. 1≤i≤n 1 − βi 1≤i≤n (k) ∗ VËy ta kÕt luËn kx − x k∞ → +∞ khi k dÇn tíi +∞. NhËn xÐt:
  62. Gi¶i tÝch sè 61 Ph−¬ng ph¸p Seidel héi tô tèt h¬n ph−¬ng ph¸p lÆp ®¬n. TiÕt kiÖm bé nhí v× hîp lý (k+1) h¬n ë chç c¸c thµnh phÇn xi võa tÝnh ®∙ ®−îc huy ®éng ®Ó tÝnh c¸c thµnh phÇn tiÕp theo. Cã thÓ cho c¸c vÝ dô chØ ra r»ng hai ph−¬ng ph¸p kh«ng ®ång thêi héi tô hoÆc ph©n kú. 6.7 Ph−¬ng ph¸p Gauss-Seidel Gi¶ sö ma trËn A cã ®−êng chÐo tréi. Nh− ph−¬ng ph¸p Jacobi ta ®−a ph−¬ng tr×nh vÒ d¹ng gi¶i b»ng ph−¬ng ph¸p lÆp. Tõ   a x + a x + + a x = b  11 1 12 2 1n n 1 a21x1 + a22x2 + + a2nxn = b2   an1x1 + an2x2 + + annxn = bn Ta chia ph−¬ng tr×nh thø i cho aii vµ chuyÓn c¸c sè h¹ng j 6= i sang vÕ ph¶i ta ®−îc a11 a12 a1n bi xi = − x1 − x2 − − xn + . aii aii aii aii Ph−¬ng tr×nh ®∙ cho t−¬ng ®−¬ng víi ph−¬ng tr×nh  a12 a1n b1 x1 = 0.x1 − x2 − − xn +  a11 a11 aii  a21 a2n b2 x2 = − x1 + 0.x2 − − xn + a22 a22 a22   x = − an1 x − an2 x − + 0.x + bn n ann 1 ann 2 n ann §Æt ma trËn B = (bij)n víi ½ 0, j = i, b = a ij − ij , j 6= i, aii vµ bi gi = . aii Khi ®ã ph−¬ng tr×nh cã d¹ng x = Bx + g. H¬n n÷a Xn kBk∞ = max |bij| < 1. 1≤i≤n i=1 B©y giê ta sö dông ph−¬ng ph¸p Seidel ¸p dông cho hÖ trªn nh− sau: Xi−1 a Xn a x(k+1) = − ij x(k+1) − ij x(k) + g . i a j a j i j=1 ii j=i ii Ph−¬ng ph¸p nµy gäi lµ ph−¬ng ph¸p Gauss‐Seidel.
  63. Gi¶i tÝch sè 62 Ch−¬ng 7 Gi¶i GÇn §óng Ph−¬ng Tr×nh Vi Ph©n Ch−¬ng nµy tr×nh bµy mét sè ph−¬ng ph¸p gi¶i bµi to¸n ph−¬ng tr×nh vi ph©n cÊp 1. §Ó gi¶i bµi to¸n nµy, ng−êi ta ph©n biÖt hai lo¹i ph−¬ng ph¸p lµ ph−¬ng ph¸p gi¶i tÝch vµ ph−¬ng ph¸p sè. C¸c ph−¬ng ph¸p gi¶i tÝch cho phÐp t×m nghiÖm gÇn ®óng ë d¹ng biÓu thøc gi¶i tÝch cßn trong c¸c ph−¬ng ph¸p sè th× t×m gÇn ®óng hµm nghiÖm y(x) t¹i mét sè ®iÓm x0, x1, , xn trªn [a, b]. 7.1 Ph−¬ng ph¸p xÊp xØ liªn tiÕp XÐt bµi to¸n Cauchy ½ y0 = f(x, y), y(0) = y0, 0 ≤ x ≤ 1. Trong ®ã f(x, y) tháa ®iÒu kiÖn Lipschitz theo y trªn miÒn më D trong kh«ng gian R2, tøc lµ |f(x, y1) − f(x, y2)| ≤ L|y1 − y2|, (x, y1), (x, y2) ∈ D, L = const. Ta lÊy λ ≥ L. −λx k y kλ= max e |y(x)|. 0≤x≤1 Z x (n+1) (n) y = y0 + f(t, y (t))dt, n = 0, 1, 2, 0 ∗ (n+1) ∗ Ta chØ ra d∙y lÆp héi tô tíi nghiÖm duy nhÊt y (x). §Æt rn+1 =k y − y k, Z x ∗ ∗ y = y0 + f(t, y (t))dt 0 Ta cã víi mçi x ∈ [0, 1] xÐt Z x |y(n+1)(x) − y∗(x)| = [f(t, y(n)(t)) − f(t, y∗(t))]dt| 0 Z x ≤ L |y(n)(t) − y∗(t)|dt 0 Z x = L eλte−λt|y(n)(t) − y∗(t)|dt 0 Z x ≤ L eλtky(n) − y∗kdt 0
  64. Gi¶i tÝch sè 63 Z x λx λt (e − 1) = Lrn e dt = Lrn . 0 λ Tõ ®ã suy ra (eλx − 1) e−λx|y(n)(x) − y∗(x)| ≤ Lr e−λx n λ 1 − e−λx 1 − e−λ = Lr ≤ Lr . n λ n λ Nh− vËy 1 − e−λ e−λx|y(n)(x) − y∗(x)| ≤ Lr . n λ LÊy max hai vÕ cña bÊt ®¼ng thøc trªn, ta cã −λ −λx (n) ∗ (1 − e ) max e |y (x) − y (x)| ≤ L rn, x∈[0,1] λ 1−e−λ tøc lµ rn+1 ≤ qrn, víi q = λ < 1. Suy ra n rn ≤ q r0. B©y giê, ta −íc l−îng r0. Ta cã 0 ∗ r0 = ky − y k −λx ∗ ∗ −λx ∗ 0 = sup e |y (x) − y (x0)| = sup e |(y ) (ξ)||x − x0| 0≤x≤1 0≤x≤1 ≤ sup e−λx||f(ξ, y∗(ξ))| 0≤x≤1 ≤ sup |f(x, y)|. (x,y)∈D §Æt M := sup(x,y)∈D |f(x, y)| th× r0 ≤ M. VËy n rn ≤ Mq . VÝ dô: Gi¶i bµi to¸n Cauchy ½ y0 = x − y, y(0) = 1, 0 ≤ x ≤ 1. ∂f(x,y) Cã f(x, y) = x − y, | ∂y | = 1, vµ do ®ã l = 1 vµ λ = L = 1. ChuÈn ®−îc x¸c ®Þnh bëi kyk = max e−x|y(x)|. x∈[0,1] §iÒu kiÖn Lipshitz lµ |f(x, y1) − f(x, y2)| ≤ |y1 − y2|.
  65. Gi¶i tÝch sè 64 MiÒn D më chøa {(x, y): x ∈ [0, 1], |y| ≤ b}, khi ®ã |f(x, y)| ≤ |x| + |y| ≤ 1 + b =: M. n −1 rn ≤ Mq , q = (1 − e ) < 1. D·y lÆp x¸c ®Þnh theo y(0)(x) = 1, Z x x2 y(1)(x) = 1 + (t − y(t))dt = 1 + − x, 0 2 Z x x3 y(2)(x) = 1 + (t − y(1)(t))dt = 1 − x + x2 − , 0 6 C«ng thøc tæng qu¸t Z x y(n+1)(x) = 1 + (t − y(n)(t))dt. 0 7.2 Ph−¬ng ph¸p chuçi nguyªn XÐt bµi to¸n Cauchy ½ y0 = f(x, y), y(0) = y0, 0 ≤ x ≤ 1. Gi¶ sö f(x, y) lµ hµm gi¶i tÝch trong l©n cËn (x0, y0), tøc lµ f(x, y) khai triÓn thµnh chuçi lòy thõa trong l©n cËn ®ã X∞ ∂m+nf(x , y ) (x − x )m(y − y )n f(x, y) = 0 0 0 0 . ∂xm∂yn m!n! m,n=0 Khi ®ã nghiÖm y∗(x) còng cã thÓ khai triÓn thµnh chuçi lòy thõa X∞ y∗(i)(x ) y∗(x) = 0 (x − x )i. i! 0 i=0 ∗ ∗ Nh­ vËy hµm nghiÖm y sÏ ®−îc x¸c ®Þnh nÕu ta tÝnh ®−îc c¸c ®¹o hµm cña y t¹i x0, vµ c¸c ®¹o hµm nµy dÔ dµng tÝnh ®−îc. Cô thÓ nh− sau: y(x0) = y0, 0 0 y (x) = f(x, y) ⇒ y (x0) = f(x0, y0), ∂f(x, y) ∂f(x, y) y”(x) = + y0(x, y) ∂x ∂y
  66. Gi¶i tÝch sè 65 ∂f(x , y ) ∂f(x , y ) ⇒ y”(x ) = 0 0 + 0 0 f(x , y ), 0 ∂x ∂y 0 0 TiÕp tôc tÝnh c¸c ®¹o hµm y(k), k = 3, 4, ta x¸c ®Þnh ®−îc hµm nghiÖm cña ph−¬ng tr×nh y(x) X∞ y(i)(x ) y(x) = 0 (x − x )i. i! 0 i=0 Nh− vËy, ph−¬ng ph¸p nµy ®¬n gi¶n nh−ng tÝnh to¸n phøc t¹p vµ b¸n kÝnh héi tô cña chuçi nghiÖm khã x¸c ®Þnh. VÝ dô: Gi¶i bµi to¸n Cauchy ½ y0 = x − y, y(0) = 1, 0 ≤ x ≤ 1. Nh− vËy f(x, y) = x − y lµ gi¶i tÝch trong l©n cËn (0, 1). Ta tÝnh c¸c ®¹o hµm y(0) = 1, y0(0) = 0 − 1 = −1, y”(x) = 1 − y0(x) ⇒ y”(0) = 2, y(3)(x) = −y”(x) ⇒ y(3)(0) = −2, y(k)(x) = −y(k−1)(x) ⇒ y(k)(0) = (−1)k2, k ≥ 2. VËy X∞ (−1)kxk y∗(x) = 1 − x + 2 k! k=2 = 2ex + x − 1. X∞ (−x)k = 1 − x + 2( − 1 + x) k! k=0 VËy nghiÖm cña bµi to¸n lµ: y(x) = 2ex + x − 1. 7.3 Ph−¬ng ph¸p Euler 7.3.1 C«ng thøc Euler
  67. Gi¶i tÝch sè 66 XÐt bµi to¸n Cauchy ½ y0 = f(x, y), y(0) = y0, a ≤ x ≤ b. §Æt vÊn ®Ò lµ t×m gÇn ®óng hµm nghiÖm y(x) t¹i mét sè ®iÓm a ≤ x0 < x1 < < xn ≤ ∗ ∗ b. Tøc lµ t×m nghiÖm yi gÇn ®óng víi y (xi) víi mäi i (ë ®©y y chØ nghiÖm ®óng). NÕu ∗ c¸c ®iÓm chia xi cµng nhiÒu th× ta cµng cã h×nh ¶nh gÇn ®óng cña hµm nghiÖm y (x). XÐt tr−êng hîp c¸c b−íc c¸ch ®Òu, tøc lµ xi+1 − xi = h, i = 0, 1, 2, , n. Tõ khai triÓn Taylor, ta cã y0(x ) y”(ξ) y(x ) = y(x ) + i (x − x ) + (x − x )2. i+1 i 1! i+1 i 2! i−1 i Suy ra hf(x , y(x )) y(x ) = y(x ) + i i + o(h2). i+1 i 1! VËy ta cã thÓ coi hf(x , y(x )) y(x ) ' y(x ) + i i . i+1 i 1! Ta cã c«ng thøc Euler nh− sau yi+1 = yi + hf(xi, yi). 7.3.2 C«ng thøc sai sè cña ph−¬ng ph¸p Euler a. Sai sè ®Þa ph−¬ng: XÐt sai sè m¾c ph¶i trªn mét b−íc víi gi¶ thiÕt b−íc tr−íc ®ã tÝnh ®óng. T¹i b−íc thø i ta xÐt hµm y(x) lµ nghiÖm cña bµi to¸n ½ y0 = f(x, y(x)), y(xi) = yi. NghiÖm ®óng cña bµi to¸n nµy hf(x , y(x )) y(x ) = y(x ) + i i + o(h2). i+1 i 1! Bëi y(xi) = yi vµ yi+1 = yi + hf(xi, yi) nªn 2 2 y(xi+1) = yi + hf(xi, yi) + o(h ) = yi+1 + o(h ). Tõ ®ã suy ra 2 y(xi+1) − yi+1 = o(h ). b. Sai sè toµn phÇn: XÐt sai sè trªn toµn ®o¹n [x0, xn]. Gi¶ sö hµm f(x, y) tháa ®iÒu kiÖn Lipshitz theo y |f(x, y1) − f(x, y2)| ≤ L|y1 − y2|,
  68. Gi¶i tÝch sè 67 vµ cã M sao cho ∂f(x, y(x)) ≤ M, x ∈ [x , x ]. ∂x 0 n Tõ c«ng thøc Euler suy ra: 1. Gi¸ trÞ gÇn ®óng theo Euler lµ yn = yn−1 + hf(xn−1, yn−1). 2. Gi¸ trÞ ®óng cña nghiÖm t¹i xn lµ Z xn y(xn) = y0 + f(t, y(t))dt. x0 B©y giê, ta ®Æt ²n = yn − y(xn), ²i = yi − y(xi), i = 0, 1, 2, , n. Ký hiÖu 4²i = ²i+1 − ²i = yi+1 − yi − (y(xi+1) − y(xi)) Z xi+1 = hf(xi, yi) − (f(t, y(t))dt x Zi xi+1 = hf(xi, yi) − f(xi, y(xi)) − (f(t, y(t)) − f(xi, yi))dt. xi Tõ ®ã suy ra |4²i = |²i+1 − ²i| Z xi+1 ≤ Lh|yi − y(xi)| + M |t − xi|dt xi Mh2 ≤ Lh|² | + . i 2 VËy Mh2 |² | ≤ (1 + Lh)|² | + , i = 0, 1, 2, , n. i+1 i 2 B©y giê xÐt Mh2 |² | ≤ (1 + Lh)|² | + n n−1 2 Mh2 Mh2 ≤ (1 + Lh){(1 + Lh)|² | + } + n−2 2 2 Mh2 = (1 + Lh)2|² | + (1 + (1 + Lh)) n−2 2
  69. Gi¶i tÝch sè 68 Mh2 ≤ (1 + Lh)n|² | + (1 + (1 + Lh) + (1 + Lh)2 + + (1 + Lh)n−1). 0 2 Bëi ²0 = y(x0) − y0 = 0, suy ra Mh2 (1 + Lh)n − 1 Mh |² | ≤ = ((1 + Lh)n − 1). n 2 1 + Lh − 1 2L Tõ bÊt ®¼ng thøc (1 + x)n 0, ∀n ta suy ra c«ng thøc sai sè Mh Mh |² | ≤ (enLh − 1) = (eL(xn−x0) − 1). n 2L 2L Cuèi cïng, ta cã c«ng thøc sai sè Mh |² | ≤ (eL(xn−x0) − 1). n 2L 7.3.3 TÝnh æn ®Þnh cña ph−¬ng ph¸p Euler d g g d Gi¶ sö gi¸ trÞ ban ®Çu ®óng lµ y0 vµ gi¸ trÞ gÇn ®óng cña nã lµ y0 sao cho |y0 − y0 | ≤ δ, δ > 0. Ta xÐt xem sai sè ban ®Çu cã bÞ khuÕch ®¹i sau n b−íc hay kh«ng. d d d yi+1 = yi + hf(xi), yi ), g g g yi+1 = yi + hf(xi), yi ). Ta cã d g d g d g |yi+1 − yi+1| ≤ |yi − yi | + h|f(xi, yi − f(xi), yi )| d g ≤ (1 + Lh)|yi − yi |. VËy d g d g |yi+1 − yi+1| ≤ (1 + Lh)|yi − yi |, ∀i. Tõ ®ã suy ra d g d g |yi+1 − yi+1| ≤ (1 + Lh)|yn−1 − yn−1| 2 d g ≤ (1 + Lh) |yn−2 − yn−2| n d g ≤ (1 + Lh) |y0 − y0| ≤ (1 + Lh)nδ ≤ enLhδ = eL(xn−x0)δ. Nh− vËy d g L(xn−x0) |yn − yn| ≤ Aδ, A = e . §iÒu nµy nãi r»ng thuËt to¸n æn ®Þnh v× sai sè ban ®Çu kh«ng bÞ khuÕch ®¹i sau n b−íc. Ph−¬ng ph¸p Euler ®¬n gi¶n, dÔ lËp tr×nh nh−ng ®é chÝnh x¸c kh«ng cao.
  70. Gi¶i tÝch sè 69 7.4 Ph−¬ng ph¸p Euler c¶i tiÕn Thay v× dïng c«ng thøc Euler ta sö dông c«ng thøc sau h y = y + (f(x , y ) − f(x , y )). i+1 i 2 i i i+1 i+1 Ph−¬ng ph¸p tiÕn hµnh nh− sau: LÊy (0) yi+1 = yi + hf(xi, yi), LÆp theo k ≥ 1, h y(k) = y + (f(x , y ) + f(x , y(k−1))). i+1 i 2 i i i+1 i+1 Khi thÊy (k) (k−1) |yi+1 − yi+1 | ≤ ² (k) th× dõng l¹i vµ lÊy yi+1 ' yi+1. 7.5 Ph−¬ng ph¸p Runge‐Kutta §Æt y1 = y0 + ∆y0 , trong ®ã ∆y0 = pr1k1(h) + + prrkr(h), ki(h) = hf(ξi, ζi); ξi = x0 + αih, α1 = 0, i = 1, 2, , r, ζi = y0 + βi1k1(h) + + βi,i−1ki−1(h). Gäi ΦR(h) := y(x0 + h) − y1 = y(x0 + h) − y(x0) − ∆y0 , (s+1) NÕu Φr (0) 6= 0, th× Xr Φ(i)(0) Φ (h) = r hi + 0(hs+1). r i! i=0 (i) Khi ®ã ta chän c¸c hÖ sè αi, βij, prj tõ ®iÒu kiÖn Φr (0) = 0 víi mäi i = 0, 1, 2, , s vµ (s+1) Φr (0) 6= 0 víi s cµng lín cµng tèt. VËy (i) (i) Φr (0) = y0 − [pr1k1(h) + + prrkr(h)], i = 0, 1, , s. Tøc lµ, ®Ó x¸c ®Þnh c¸c hÖ sè ta cÇn gi¶i hÖ phi tuyÕn sau (i) pr1k1(h) + + prrkr(h) = y0 , i = 0, 1, 2, , s. C¸c tr−êng hîp cña ph−¬ng ph¸p Runge‐Kutta
  71. Gi¶i tÝch sè 70 a. Tr−êng hîp r = 1 ta nhËn ®−îc c«ng thøc Euler y1 = y0 + hf(x0, y0). b. Tr−êng hîp r = 2 ta nhËn ®−îc c«ng thøc Euler c¶i tiÕn y0 := y0 + hf(x0, y0), f(x , y ) + f(x , y ) y = y + h 0 0 1 0 . 1 0 2 c. Tr−êng hîp r = 4 cã c«ng thøc RK4 sau 1 ∆y = (k + 2k + 2k + k ), 0 6 1 2 3 4 k1 = hf(x0, y0), h k k = hf(x + , y + 1 ), 2 0 2 0 2 h k k = hf(x , + , y + 2 ), 3 0 2 0 2 k4 = hf(fx0 + h, y0 + k3). NhËn xÐt: 1. Sai sè ®Þa ph−¬ng cña c«ng thøc (RK4) lµ Φ(5)(η) R = h5 4 , η ∈ [a, b]. 120 2. Ph−¬ng ph¸p RK4 dÔ lËp tr×nh, ®é chÝnh x¸c cao, t−¬ng ®èi ®¬n gi¶n. VÝ dô: Dïng ph−¬ng ph¸p Runge‐Kutta (RK4) gi¶i gÇn ®óng ph−¬ng tr×nh vi ph©n sau víi n = 5. ½ y0 = x − y, y(0) = 1, 0 ≤ x ≤ 1. Chia [0, 1] thµnh 5 ®o¹n bëi xi = 0.2 × i, i = 0, 1, 2, 3, 4, 5. Ta cã: y0 = 1, ∆y0 = k1 + 2k2 + 2k3 + k4, trong ®ã: k1 = 0.2 × (0 − 1) = −0.2, k2 = 0.2 × (0 + 0.1 − (1 + 0.1)) = −0.2, k3 = 0.2 × (0 + 0.1 − (1 + 0.2/2)), k4 = 0.2 × (0 + 0.2 − (1 + k3)).
  72. Gi¶i tÝch sè 71 Ta tÝnh ®−îc y1 = y0 + ∆0. T−¬ng tù ∆y1 = k1 + 2k2 + 2k3 + k4, trong ®ã: k1 = 0.2 × (x1 + 0.1 − y1), k2 = 0.2 × (x1 + 0.1 − (y1 + k1/2)), k3 = 0.2 × (x1 + 0.1 − (y1 + k2/2)), k4 = 0.2 × (x1 + 0.2 − (y1 + k3)). VËy ta tÝnh ®−îc y2 = y1 + ∆y1 . TiÕp tôc qu¸ tr×nh cho tíi khi tÝnh ®−îc y5 th× dõng thuËt to¸n vµ viÕt kÕt qu¶ thµnh b¶ng.
  73. Gi¶i tÝch sè 72 Tµi liÖu tham kh¶o 1. P. K. Anh, Gi¶i tÝch sè, Nhµ xuÊt b¶n §¹i häc Quèc gia Hµ Néi, 1996. 2. T. T. Ai, Ph−¬ng ph¸p sè, Nhµ xuÊt b¶n §¹i häc Quèc gia Hµ Néi, 2001. 3. N. Bacvalop, Methodes Numeriques, 1976. 4. I. C Berezin, H. P. Jicop, Ph−¬ng ph¸p tÝnh, TiÕng Nga, NXB. Mockva, 1959. 5. B. F. Demiovich, Computational Mathematics, Mir Publishers, Moscow, 1973. 6. T. V. §Ünh, Ph−¬ng ph¸p tÝnh, Nhµ xuÊt b¶n Gi¸o dôc, 1998. 7. P. V. H¹p, L. §. ThÞnh, Ph−¬ng Ph¸p TÝnh, nhµ xuÊt b¶n §¹i häc vµ Trung häc chuyªn nghiÖp, Hµ Néi, 1977. 8. H. X. HuÊn, Gi¸o tr×nh c¸c ph−¬ng ph¸p sè, Nhµ xuÊt b¶n §¹i häc Quèc gia Hµ Néi, 2004. 9. Gi¸o tr×nh gi¶i tÝch sè, §¹i häc KHTN‐TP. Hå ChÝ Minh.