Giáo trình Lập trình Turbo C (Phần 2)

Ch−¬ng 8 : Gi¶i gÇn ®óng ph−¬ng tr×nh ®¹i sè

vµ siªu viÖt

§1.Kh¸i niÖm chung

NÕu ph−¬ng tr×nh ®¹i sè hay siªu viÖt kh¸ phøc t¹p th× Ýt khi t×m ®−îc nghiÖm

®óng.Bëi vËy viÖc t×m nghiÖm gÇn ®óng vµ −íc l−îng sai sè lµ rÊt cÇn thiÕt.

Ta xÐt ph−¬ng tr×nh :

f(x) = 0

(1)

víi f(x) lµ hµm cho tr−íc cña biÕn x.Chóng ta cÇn t×m gi¸ trÞ gÇn ®óng cña nghiÖm cña

ph−¬ng tr×nh nµy.

Qu¸ tr×nh gi¶i th−êng chia lµm hai b−íc: b−íc s¬ bé vµ b−íc kiÖn toµn nghiÖm.

B−íc gi¶i s¬ bé cã 3 nhiÖm vô:v©y nghiÖm, t¸ch nghiÖm vµ thu hÑp kho¶ng chøa

nghiÖm.

V©y nghiÖm lµ t×m xem c¸c nghiÖm cña ph−¬ng tr×nh cã thÓ n»m trªn nh÷ng ®o¹n

nµo cña trôc x.T¸ch nghiÖm lµ t×m c¸c kho¶ng chøa nghiÖm soa cho trong mçi kho¶ng chØ

cã ®óng mét nghiÖm.Thu hÑp kho¶ng chøa nghiÖm lµ lµm cho kho¶ng chøa nghiÖm cµng

nhá cµng tèt.Sau b−íc s¬ bé ta cã kho¶ng chøa nghiÖm ®ñ nhá.

B−íc kiÖn toµn nghiÖm t×m c¸c nghiÖm gÇn ®óng theo yªu cÇu ®Æt ra.

Cã rÊt nhiÒu ph−¬ng ph¸p x¸c ®Þnh nghiÖm cña (1).Sau ®©y chóng ta xÐt tõng ph−¬ng

ph¸p.

§2.Ph−¬ng ph¸p lÆp ®¬n

Gi¶ sö ph−¬ng tr×nh (1) ®−îc ®−a vÒ d¹ng t−¬ng ®−¬ng :

x = g(x)

tõ gi¸ trÞ x_onµo ®ã gäi lµ gi¸ trÞ lÆp ®Çu tiªn ta lËp d·y xÊp xØ b»ng c«ng thøc :

x_n= g(x_n-1) (3)

(2)

víi n = 1,2,....

Hµm g(x) ®−îc gäi lµ hµm lÆp.NÕu d·y x_n→ α khi n →∝ th× ta nãi phÐp lÆp (3) héi

tô.

x₁

x_o

x_ox₁

H×nh b

H×nh a

Ta cã ®Þnh lÝ:XÐt ph−¬ng ph¸p lÆp (3),gi¶ sö :

- [a,b] lµ kho¶ng ph©n li nghiÖm α cña ph−¬ng tr×nh (1) tøc lµ cña (2)

- mäi x_ntÝnh theo (3) ®Òu thuéc [a,b]

- g(x) cã ®¹o hµm tho¶ m·n :

87

′

g (x) ≤ q <1 ,a < x < b

(4)

trong ®ã q lµ mét h»ng sè th× ph−¬ng ph¸p lÆp (3) héi tô

Ta cã thÓ minh ho¹ phÐp lÆp trªn b»ng h×nh vÏ a vµ b.

C¸ch ®−a ph−¬ng tr×nh f(x) = 0 vÒ d¹ng x = g(x) ®−îc thùc hiÖn nh− sau:ta thÊy f(x)

= 0 cã thÓ biÕn ®æi thµnh x = x + λf(x) víi λ ≠ 0.Sau ®ã ®Æt x + λf(x) = g(x) sao cho ®iÒu

kiÖn (4) ®−îc tho¶ m·n.

VÝ dô:xÐt ph−¬ng tr×nh

x³+ x - 1000 = 0

Sau b−íc gi¶i s¬ bé ta cã nghiÖm x₁∈ ( 9,10 )

NÕu ®−a ph−¬ng tr×nh vÒ d¹ng:

x = 1000 - x³= g(x)

th× dÔ thÊy | g^'(x) | > 1 trong kho¶ng ( 9,10 ) nªn kh«ng tho¶ m·n ®iÒu kiÖn (4)

Chóng ta ®−a ph−¬ng tr×nh vÒ d¹ng

x = ³1000 − x

th× ta thÊy ®iÒu kiÖn (4) ®−îc tho¶ m·n.X©y dùng d·y xÊp xØ

3

=

x_n+11000−x_n

víi x_ochän bÊt k× trong ( 9,10 )

Trªn c¬ së ph−¬ng ph¸p nµy chóng ta cã c¸c ch−¬ng tr×nh tÝnh to¸n sau:

Ch−¬ng tr×nh gi¶i ph−¬ng tr×nh exp((1/3)*ln(1000-x)) víi sè lÇn lÆp cho tr−íc

Ch−¬ng tr×nh 8-1

//lap don

#include <conio.h>

#include <stdio.h>

#include <math.h>

void main()

{

int i,n;

float x,x0;

float f(float);

clrscr();

printf("Cho so lan lap n = ");

scanf("%d",&n);

printf("Cho gia tri ban dau cua nghiem x0 = ");

scanf("%f",&x0);

x=x0;

for (i=1;i<=n;i++)

x=f(x);

printf("Nghiem cua phuong trinh la :%.4f",x);

getch();

}

float f(float x)

{

float a=exp((1./3.)*log(1000-x));

return(a);

88

}

vµ ch−¬ng tr×nh gi¶i bµi to¸n b»ng ph−¬ng ph¸p lÆp víi sai sè cho tr−íc

Ch−¬ng tr×nh 8-2

//lap don

#include <conio.h>

#include <stdio.h>

#include <math.h>

void main()

{

int i;

float epsi,x,x0,y;

float f(float);

clrscr();

printf("Cho sai so epsilon = ");

scanf("%f",&epsi);

printf("Cho gia tri ban dau cua nghiem x0 = ");

scanf("%f",&x0);

x=x0;

y=f(x);

if (abs(y-x)>epsi)

{

x=y;

y=f(x);

}

printf("Nghiem cua phuong trinh la %.6f",y);

getch();

}

float f(float x)

{

float a=exp((1./3.)*log(1000-x));

return(a);

}

Cho gi¸ trÞ ®Çu x_o= 1.KÕt qu¶ tÝnh to¸n x = 9.966555

§3.Ph−¬ng ph¸p chia ®«i cung

89

Gi¶ sö cho ph−¬ng tr×nh f(x) = 0 víi f(x)

liªn tôc trªn ®o¹n [a,b] vµ f(a).f(b) < 0.Chia ®o¹n

[a,b] thµnh 2 phÇn bëi chÝnh ®iÓm chia (a + b)/2.

1.NÕu f((a+b)/2) = 0 th× ξ = (a+b)/2

2.NÕu f((a+b)/2) ≠ 0 th× chän [ a,(a + b)/2 ]

hay [ (a + b)/2,b ] mµ gi¸ trÞ hµm hai ®Çu tr¸i dÊu

vµ kÝ hiÖu lµ [a₁,b₁].§èi víi [a₁,b₁] ta l¹i tiÕn hµnh

nh− [a,b]

y

b

a

ξ

b₁

x

C¸ch lµm trªn ®−îc m« t¶ trong ch−¬ng

tr×nh sau dïng ®Ó t×m nghiÖm cña ph−¬ng tr×nh :

x⁴+ 2x³- x - 1 = 0

trªn ®o¹n [0,1]

Ch−¬ng tr×nh 8-3

//chia doi cung

#include <conio.h>

#include <stdio.h>

#include <math.h>

#define epsi 0.00001

void main()

{

float x0,x1,x2;

float y0,y1,y2;

float f(float);

int maxlap,demlap;

clrscr();

printf("Tim nghiem cua phuong trinh phi tuyen");

printf("\nbang cach chia doi cung\n");

printf("Cho cac gia tri x0,x1,maxlap\n");

printf("Cho gia tri x0 = ");

scanf("%f",&x0);

printf("Cho gia tri x1 = ");

scanf("%f",&x1);

printf("Cho so lan lap maxlap = ");

scanf("%d",&maxlap);

y0=f(x0);

y1=f(x1);

if ((y0*y1)>0)

{

printf("Nghiem khong nam trong doan x0 - x1\n");

printf(" x0 = %.2f\n",x0);

printf(" x1 = %.2f\n",x1);

printf(" f(x0) = %.2f\n",y0);

printf(" f(x1) = %.2f\n",y1);

}

demlap=0;

do

{

90

x2=(x0+x1)/2;

y2=f(x2);

y0=f(x0);

if (y0*y2>0)

x0=x2;

else

x1=x2;

demlap=demlap+1;

}

while(((abs((y2-y0))>epsi)||(demlap<maxlap)));

if (demlap>maxlap)

{

printf("Phep lap khong hoi tu sau %d lan lap ",maxlap);

printf(" x0 = %.2f\n",x0);

printf(" x1 = %.2f\n",x1);

printf(" f(x2) = %.2f\n",y2);

}

else

{

printf("Phep lap hoi tu sau %d lan lap\n",demlap);

printf("Nghiem x = %.2f",x2);

}

getch();

}

float f(float x)

{

float a=x*x*x*x+2*x*x*x-x-1 ;

return(a);

}

KÕt qu¶ tÝnh cho nghiÖm:x = 0.87

§4.Ph−¬ng ph¸p d©y cung

Gi¶ sö f(x) liªn tôc trªn trªn ®o¹n [a,b] vµ f(a).f(b) < 0.CÇn t×m nghiÖm cña f(x) =

0.§Ó x¸c ®Þnh ta xem f(a) < 0 vµ f(b) > 0.Khi ®ã thay v× chia ®«i ®o¹n [a,b] ta chia [a,b] theo

tØ lÖ -f(a)/f(b).§iÒu ®ã cho ta nghiÖm gÇn ®óng :

x₁= a + h₁

Trong ®ã

−f(a)

−f(a)+f(b)

=

(b−a)

h₁

TiÕp theo dïng c¸ch ®ã víi ®o¹n [ a,x₁] hay [ x₁,b] mµ hai ®Çu hµm nhËn gi¸ trÞ tr¸i

dÊu ta ®−îc nghiÖm gÇn ®óng x₂v.v.

VÒ mÆ h×nh häc,ph−¬ng ph¸p nµy cã nghÜa lµ kÎ d©y cung cña ®−êng cong f(x) qua hai ®iÓm

A[a,f(a)] vµ B[b,f(b)].ThËt vËy ph−¬ng tr×nh d©y cung AB cã d¹ng :

91

x − a

y − f (a)

b − a f (b) − f (a)

=

Cho x = x₁y = 0 ta cã

B

b

f(a)

f(b)−f(a)

=

(b−a)

x₁a−

Trªn c¬ së cña ph−¬ng ph¸p ta cã ch−¬ng tr×nh

tÝnh nghiÖm cña ph−¬ng tr×nh

x⁴+ 2x³- x - 1 = 0

a

x₁

ξ

trªn ®o¹n [0,1]

A

Ch−¬ng tr×nh 8-4

//phuong phap day cung

#include <conio.h>

#include <stdio.h>

#include <math.h>

#define epsi 0.00001

void main()

{

float a,b,fa,fb,dx,x;

float f(float);

clrscr();

printf("Tim nghiem cua phuong trinh phi tuyen\n");

printf("bang phuong phap day cung\n");

printf("Cho cac gia tri a,b\n");

printf("Cho gia tri cua a = ");

scanf("%f",&a);

printf("Cho gia tri cua b = ");

scanf("%f",&b);

fa=f(a);

fb=f(b);

dx=fa*(b-a)/(fa-fb);

while (fabs(dx)>epsi)

{

x=a+dx;

fa=f(x);

if((fa*fb)<=0)

a=x;

else

b=x;

fa=f(a);

fb=f(b);

dx=fa*(b-a)/(fa-fb);

}

92

printf("Nghiem x = %.3f",x);

getch();

}

float f(float x)

{

float e=x*x*x*x+2*x*x*x-x-1;

return(e);

}

KÕt qu¶ tÝnh cho nghiÖm:x = 0.876

§5.Ph−¬ng ph¸p lÆp Newton

Ph−¬ng ph¸p lÆp Newton (cßn gäi lµ

ph−¬ng ph¸p tiÕp tuyÕn) ®−îc dïng nhiÒu v× nã héi

tô nhanh.Gi¶ sö f(x) cã nghiÖm lµ ξ ®· ®−îc t¸ch

trªn ®o¹n [a,b] ®ång thêi f'(x) vµ f"(x) liªn tôc vµ

gi÷ nguyªn dÊu trªn ®o¹n [a,b].Khi ®· t×m ®−îc

xÊp xØ nµo ®ã x_n∈ [a,b] ta cã thÓ kiÖn toµn nã theo

ph−¬ng ph¸p Newton.Tõ mót B ta vÏ tiÕp tuyÕn víi

®−êng cong.Ph−¬ng tr×nh ®−êng tiÕp tuyÕn lµ

a

x₁

b=x_o

′

y − f (x₀) = f (b)(x − x₀)

TiÕp tuyÕn nµy c¾t trôc hoµnh t¹i ®iÓm cã

y=0,nghÜa lµ :

′

− f(x₀) = f (b)(x₁− x₀)

hay :

f(x₀)

x₁= x₀−

′

f (x₀)

Tõ x₁ta l¹i tiÕp tôc vÏ tiÕp tuyÕn víi ®−êng cong th× giao ®iÓm x_isÏ tiÕn tíi nghiÖm cña

ph−¬ng tr×nh.

ViÖc chän ®iÓm ban ®Çu x_orÊt quan träng.Trªn h×nh vÏ trªn ta thÊy nÕu chän ®iÓm

ban ®Çu x_o= a th× tiÕp tuyÕn sÏ c¾t trôc t¹i mét ®iÓm n»m ngoµi ®o¹n [a,b].Chän x_o= b sÏ

thuËn lîi cho viÖc tÝnh to¸n.Chóng ta cã ®Þnh lÝ :

NÕu f(a).f(b) < 0 ; f(x) vµ f"(x) kh¸c kh«ng vµ gi÷ nguyªn dÊu x¸c ®Þnh khi x ∈ [a,b]

th× xuÊt ph¸t tõ x_o∈ [a,b] tho¶ m·n ®iÒu kiÖn f(x_o).f″(x_o) > 0 cã thÓ tÝnh theo ph−¬ng ph¸p

Newton nghiÖm ξ duy nhÊt víi ®é chÝnh x¸c tuú ý.

Khi dïng ph−¬ng ph¸p Newton cÇn lÊy x_olµ ®Çu mót cña ®o¹n [a,b] ®Ó t¹i ®ã

f(x_o).f"(x_o) > 0.¸p dông lÝ thuyÕt trªn chóng ta x©y dùng ch−¬ng tr×nh tÝnh sau:

Ch−¬ng tr×nh 8-5

//phuong phap Newton

#include <conio.h>

#include <stdio.h>

93

#include <math.h>

#include <stdlib.h>

#define n 50

#define epsi 1e-5

void main()

{

float t,x0;

float x[n];

int i;

float f(float);

float daoham(float);

clrscr();

printf("Tim nghiem cua phuong trinh phi tuyen\n");

printf("bang phuong phap lap Newton\n");

printf("Cho gia tri cua x0 = ");

scanf("%f",&x0);

i=1;

x[i]=x0;

do

{

x[i+1] = x[i]-f(x[i])/daoham(x[i]);

t = fabs(x[i+1]-x[i]);

x[i]=x[i+1];

i=i+1;

if (i>100)

{

printf("Bai toan khong hoi tu\n");

getch();

exit(1);

}

else

;

}

while (t>=epsi);

printf("Nghiem x = %.5f",x[i]);

getch();

}

float f(float x)

{

float a=x*x-x-2;

return(a);

}

float daoham(float x)

{

float d=2*x-1;

return(d);

94

}

Ch−¬ng tr×nh nµy ®−îc dïng x¸c ®Þnh nghiÖm cña hµm ®· ®−îc ®Þnh nghÜa trong

function.Trong tr−êng hîp nµy ph−¬ng tr×nh ®ã lµ:x²- x -1 = 0.KÕt qu¶ tÝnh víi gi¸ trÞ ®Çu x_o

= 0 cho nghiÖm x = 2.

§6.Ph−¬ng ph¸p Muller

Trong ph−¬ng ph¸p d©y cung khi t×m nghiÖm trong ®o¹n [a,b] ta xÊp xØ hµm b»ng

mét ®−êng th¼ng.Tuy nhiªn ®Ó gi¶m l−îng tÝnh to¸n vµ ®Ó nghiÖm héi tô nhanh h¬n ta cã

thÓ dïng ph−¬ng ph¸p Muller.Néi dung cña ph−¬ng ph¸p nµy lµ thay hµm trong ®o¹n [a,b]

b»ng mét ®−êng cong bËc 2 mµ ta hoµn toµn cã thÓ t×m nghiªm chÝn x¸c cña nã.Gäi c¸c

®iÓm ®ã cã hoµnh ®é lÇn l−ît lµ a = x₂,b = x₁vµ ta chän thªm mét ®iÓm x₀n»m trong ®o¹n

[x₂,x₁].Gäi

h₁= x₁- x₀

h₂= x₀- x₂

v = x - x₀

f(x₀) = f₀

x₀,f₀

x₁,f₁

f(x₁) = f₁

f(x₂) = f₂

f(x)

h₂

γ =

h₁

av²+bv+c

Qua 3 ®iÓm nµy ta cã mét ®−êng parabol :

x₂,f₂

h₁

h₂

y = av²+ bv + c

Ta t×m c¸c hÖ sè a,b,c tõ c¸c gi¸ trÞ ®· biÕt v:

v = 0(x = x₀) a(0)²+ b(0) + c = f₀

v = h₁(x = x₁) ah₁²+ bh₁+ c = f₁

v = h₂(x = x₂) ah²₂+ bh₂+ c = f₂

Tõ ®ã ta cã :

γf₁− f₀(1+ γ) + f₂

a =

γh₁²(1+ γ)

f₁− f₀− ah₁²

b =

h₁

c = f₀

Sau ®ã ta t×m nghiÖm cña ph−¬ng tr×nh av²+ bv + c = 0 vµ cã :

2c

n_1,2= x₀−

b ± b²− 4ac

TiÕp ®ã ta chän nghiÖm gÇn x₀nhÊt lµm mét trong 3 ®iÓm ®Ó tÝnh xÊp xØ míi.C¸c ®iÓm nµy

®−îc chän gÇn nhau nhÊt.

TiÕp tôc qu¸ tr×nh tÝnh ®Õn khi ®¹t ®é chÝnh x¸c yªu cÇu th× dõng l¹i.

VÝ dô:T×m nghiÖm cña hµm f(x) = sin(x) - x/2 trong ®o¹n [1.8,2.2].Ta chän x₀= 2

Ta cã :

x₀= 2

x₁= 2.2

x₂= 1.8

f(x₀) = -0.0907

f(x₁) = -0.2915

f(x₂) = 0.07385

h₁= 0.2

h₂= 0.2

γ = 1

VËy th× :

95

1×(−0.2915) − (−0.0907)×(1+1) + 0.07385

1×0.2²×(1+1)

a =

b =

= −0.45312

− 0.2915 − (−0.097) − (−0.45312)×0.2²

= −0.91338

0.2

c = −0.0907

Ta cã nghiÖm gÇn x₀nhÊt lµ :

2×(−0.0907)

− 0.91338 − (−0.91338)²− 4×(−0.45312)×(−0.0907)

n₁= 2.0 −

= 1.89526

Víi lÇn lÆp thø hai ta cã :

x₀= 1.89526

x₁= 2.0

x₂= 1.8

f(x₀) = 1.9184×10^-4

h₁= 0.10474

f(x₁) = -0.0907

f(x₂) = 0.07385

h₂= 0.09526

γ = 0.9095

VËy th× :

0.9095×(−0.0907) − (1.9184×10⁻⁴)×1.9095 + 0.07385

0.9095×0.10474²×1.9095

a =

= −0.4728

− 0.0907 −1.9184×10⁻⁴− (−0.4728)×0.10474²

b =

= −0.81826

0.10474

c = 1.9184×10⁻⁴

Ta cã nghiÖm gÇn x₀nhÊt lµ :

2×1.9184×10⁻⁴

n₁= 1.89526 −

= 1.89594

− 0.81826 − (0.81826)²− 4×(−0.4728)×1.9184×10⁻⁴

Ta cã thÓ lÊy n₁= 1.895494 lµm nghiÖm cña bµi to¸n

Ch−¬ng tr×nh gi¶i bµi to¸n b»ng ph−¬ng ph¸p Muller nh− sau:

Ch−¬ng tr×nh 8-6

//phuong phap Muller

#include <conio.h>

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

void main()

{

float x0,x1,x2,h1,h2,eps;

float a,b,c,gamma,n1,n2,xr;

int dem;

float f(float);

clrscr();

printf("PHUONG PHAP MULLER\n");

printf("\n");

printf("Cho khoang can tim nghiem [a,b]\n");

printf("Cho gia tri duoi a = ");

scanf("%f",&x2);

96

printf("Cho gia tri tren b = ");

scanf("%f",&x1);

if (f(x1)*f(x2)>0)

{

printf("\n");

printf("Nghiem khong nam trong doan nay\n");

getch();

exit(1);

}

eps=1e-5;

x0=(x1+x2)/2;

dem=0;

do

{

dem=dem+1;

h1=x1-x0;

h2=x0-x2;

gamma=h2/h1;

a=(gamma*f(x1)-

f(x0)*(1+gamma)+f(x2))/(gamma*(h1*h1)*(1+gamma));

b=(f(x1)-f(x0)-a*(h1*h1))/h1;

c=f(x0);

if ((a==0)&&(b!=0))

{

n1=-c/b;

n2=n1;

}

if ((a!=0)&&(b==0))

{

n1=(-sqrt(-c/a));

n2=(sqrt(-c/a));

}

if ((a!=0)&&(b!=0))

{

n1=x0-2*c/(b+(sqrt(b*b-4*a*c)));

n2=x0-2*c/(b-(sqrt(b*b-4*a*c)));

}

if (fabs(n1-x0)>fabs(n2-x0))

xr=n2;

else

xr=n1;

if (xr>x0)

{

x2=x0;

x0=xr;

}

else

{

x1=x0;

x0=xr;

97

}

while (fabs(f(xr))>=eps);

printf("\n");

printf("Phuong trinh co nghiem x = %.5f sau %d lan lap",xr,dem);

getch();

}

float f(float x)

{

float a=sin(x)-x/2;

return(a);

}

§7.Ph−¬ng ph¸p lÆp Bernoulli

Cã nhiÒu ph−¬ng ph¸p ®Ó t×m nghiÖm cña mét ®a thøc.Ta xÐt ph−¬ng tr×nh :

a_oxⁿ+ a₁x^n-1+ ⋅⋅⋅ + a_n= 0

NghiÖm cña ph−¬ng tr×nh trªn tho¶ m·n ®Þnh lÝ:NÕu max{| a₁|,| a₂|,...,| a_n|} = A th× c¸c

nghiÖm cña ph−¬ng tr×nh tho¶ m·n ®iÒu kiÖn | x | < 1 + A/ | a₀|

Ph−¬ng ph¸p Bernoulli cho phÐp tÝnh to¸n nghiÖm lín nhÊt α cña mét ®a thøc P_n(x)

cã n nghiÖm thùc ph©n biÖt.Sau khi t×m ®−îc nghiÖm lín nhÊt α ta chia ®a thøc P_n(x) cho (x

- α) vµ nhËn ®−îc ®a thøc míi Q_n-1(x).TiÕp tôc dïng ph−¬ng ph¸p Bernoulli ®Ó t×m nghiÖm

lín nhÊt cña Q_n-1(x).Sau ®ã l¹i tiÕp tôc c¸c b−íc trªn cho ®Õn khi t×m hÕt c¸c nghiÖm cña

P_n(x).

Chóng ta kh¶o s¸t ph−¬ng tr×nh ph−¬ng tr×nh sai ph©n ϕ cã d¹ng nh− sau :

ϕ = a_oy_k+n+ a₁y_k+n-1+.....+ a_ny_k= 0

§©y lµ mét ph−¬ng tr×nh sai ph©n tuyªn tÝnh hÖ sè h»ng.Khi cho tr−íc c¸c gi¸ trÞ ®Çu

(1)

y_o,y₁,..y_n-1ta t×m ®−îc c¸c gi¸ trÞ y_n,y_n+1,..Chóng ®−îc gäi lµ nghiÖm cña ph−¬ng tr×nh sai

ph©n tuyÕn tÝnh (1).

§a thøc

P_n(x) = a₀xⁿ+ a₁x^n-1+..+a_n-1x + a_n

(2)

víi cïng mét hÖ sè a_inh− (1) ®−îc gäi lµ ®a thøc ®Æc tÝnh cña ph−¬ng tr×nh sai ph©n tuyÕn

tÝnh (1).NÕu (2) cã n nghiÖm ph©n biÖt x_1,x₂,..,x_nth× (1) cã c¸c nghiÖm riªng lµ

k

x_i

=

y_i

NÕu y_ilµ c¸c nghiÖm cña ph−¬ng tr×nh sai ph©n lµ tuyÕn tÝnh (1),th×

k

^k+....+

(3)

=

+

y_k

c₁x₁c₂x₂

c_nx_n

víi c¸c hÖ sè c_ibÊt k× còng lµ nghiÖm cña ph−¬ng tr×nh sai ph©n tuyÕn tÝnh hÖ sè h»ng (1).

NÕu c¸c nghiÖm lµ sao cho :

| x₁| ≥ | x₂| ≥...| x_n|

VËy th×

vµ

k

^k[1

]

c₁x₂

=

+...

⁺c₂x₁

(

y_k

)

c₁x₁

=

^k+1+...

k+1

c₁x₁

₊c₁x₂

y_k+1

[1

(

)

]

c₂x₁

98

^k+1+...

^k+...

c₂x₂

(

[1+

do ®ã :

)

]

y_k+1

y_k

c₁x₁

=

x₁

c₂x₂

(

)

]

c₁x₁

do

nªn:

x₁> x₂

k

,

^k.......→

x₂

x₁

x₂

x₁

k→∞

(

) (

)

0 khi

vËy th× :

y_k+1

y_k

→∞ khi k→∞

y_k+1

y_k

NghÜa lµ :

=

x₁lim

k→∞

NÕu ph−¬ng tr×nh vi ph©n gåm n+1 hÖ sè,mét nghiÖm riªng y_kcã thÓ ®−îc x¸c ®Þnh

tõ n gi¸ trÞ y_k-1,y_k-2,...,y_n-1.§iÒu cho phÐp tÝnh to¸n b»ng c¸ch truy håi c¸c

nghiÖm riªng cña ph−¬ng tr×nh vi ph©n.

§Ó tÝnh nghiÖm lín nhÊt cña ®a thøc,ta xuÊt ph¸t tõ c¸c nghiÖm riªng y₁= 0,y₁=

0,..,y_n=1 ®Ó tÝnh y_n+1.C¸ch tÝnh nµy ®−îc tiÕp tôc ®Ó tÝnh y_n+2xuÊt ph¸t tõ y₁= 0,y₂=

0,..,y_n+1vµ tiÕp tôc cho ®Õn khi y_k+1/y_kkh«ng biÕn ®æi n÷a.TrÞ sè cña y_k+n®−îc tÝnh theo

c«ng thøc truy håi :

(4)

_{= −}1

+ ...+

y_k+n

y

)

a_n

(a₁

k+n−1

k

a_o

VÝ dô:TÝnh nghiÖm cña ®a thøc P_n(x) = P₃(x) = x³- 10x²+ 31x - 30.Nh− vËy a_o= 1,a₁

= -10,a₂= 31 vµ a₃= -30.Ph−¬ng tr×nh sai ph©n t−¬ng øng lµ :

y_k+3-10y_k+2+ 31y_k+1- 30y_k= 0

Ta cho tr−íc c¸c gi¸ trÞ y₁= 0 ; y₂= 0 vµ y₃= 1.Theo (4) ta tÝnh ®−îc :

y₄= - (-10y₃+ 31y₂- 30y₁) = 10

y₅= - (-10y₄+ 31y₃- 30y₂) = 69

y₆= - (-10y₅+ 31y₅- 30y₃) = 410

y₇= - (-10y₆+ 31y₅- 30y₄) = 2261

y₈= - (-10y₇+ 31y₆- 30y₅) = 11970

y₉= - (-10y₈+ 31y₇- 30y₆) = 61909

y₁₀= - (-10y₉+ 31y₈- 30y₈) = 315850

y₁₁= - (-10y₁₀+ 31y₉- 30y₈) = 1598421

y₁₂= - (-10y₁₁+ 31y₁₀- 30y₉) = 8050130

y₁₃= - (-10y₁₂+ 31y₁₁- 30y₁₀) = 40425749

y₁₄= - (-10y₁₃+ 31y₁₂- 30y₁₁) = 202656090

y₁₅= - (-10y₁₄+ 31y₁₃- 30y₁₂) = 1014866581

y₁₆= - (-10y₁₅+ 31y₁₄- 30y₁₃) = 5079099490

y₁₇= - (-10y₁₆+ 31y₁₅- 30y₁₄) = 24409813589

y₁₈= - (-10y₁₇+ 31y₁₆- 30y₁₅) = 127092049130

y₁₉= - (-10y₁₈+ 31y₁₇- 30y₁₆) = 635589254740

TØ sè c¸c sè y_k+1/y_klËp thµnh d·y :

10 ; 6.9 ; 5.942 ; 5.5146 ; 5.2941 ; 5.172 ; 5.1018 ; 5.0607 ; 5.0363 ; 5.0218 ; 5.013 ;

5.0078 ; 5.0047 ; 5.0028 ; 5.0017 ; 5.001

nghÜa lµ chóng sÏ héi tô tíi nghiÖm lín nhÊt lµ 5 cña ®a thøc

Ch−¬ng tr×nh 8-7

//phuong phap Bernoulli

#include <conio.h>

#include <stdio.h>

99

#include <math.h>

#include <stdlib.h>

#define max 50

void main()

{

float a[max],y[max];

int k,j,i,n,l;

float s,e1,e2,x0,x1,x;

clrscr();

printf("Cho bac cua da thuc can tim nghiem n = ");

scanf("%d",&n);

e1=1e-5;

printf("Cho cac he so cua da thuc can tim nghiem\n");

for (i=0;i<=n;i++)

{

printf("a[%d] = ",i);

scanf("%f",&a[i]);

}

for (k=0;k<=n;k++)

a[k]=a[k]/a[0];

tt: x1=0;

for (k=2;k<=n;k++)

y[k]=0;

y[1]=1;

l=0;

do

{

l=l+1;

s=0;

for (k=1;k<=n;k++)

s=s+y[k]*a[k];

y[0]=-s;

x=y[0]/y[1];

e2=fabs(x1 - x);

x1=x;

for (k=n;k>=1;k--)

y[k]=y[k-1];

}

while((l<=50)||(e2>=e1));

if(e2>=e1)

{

printf("Khong hoi tu");

getch();

exit(1);

}

else

printf("Nghiem x = %.4f\n",x);

n=n-1;

100

if (n!=0)

{

a[1]=a[1]+x;

for (k=2;k<=n;k++)

a[k]=a[k]+x*a[k-1];

goto tt;

}

getch();

}

KÕt qu¶ nghiÖm cña ®a thøc x³- 10x²+ 31x - 30 lµ:5 ; 3 vµ 2

§8.Ph−¬ng ph¸p lÆp Birge - Viette

C¸c nghiÖm thùc,®¬n gi¶n cña mét ®a thøc P_n(x) ®−îc tÝnh to¸n khi sö dông ph−¬ng

ph¸p Newton

(x )

(1)

₋P_n

i

=

x_i+1x_i

′

P (x

)

n

i

§Ó b¾t ®Çu tÝnh to¸n cÇn chän mét gi¸ trÞ ban ®Çu x_o.Chóng ta cã thÓ chän mét gi¸ trÞ

x_onµo ®ã,vÝ dô :

a_n

= −

x_o

a

n−1

vµ tÝnh tiÕp c¸c gi¸ trÞ sau :

(x )

₋P_n

o

=

x₁x_o

′

P (x

)

n

o

(x )

₋P_n

1

=

x₂x₁

′

P (x

)

n

1

TiÕp theo cã thÓ ®¸nh gi¸ P_n(x_i) theo thuËt to¸n Horner :

P₀= a₀

P₁= P₀x_i+ a₁

P₂= P₁x_i+ a₂

P₃= P₂x_i+ a₃

..................

(2)

(3)

P(x_i) = P_n= P_n-1x_i+ a_n

MÆt kh¸c khi chia ®a thøc P_n(x) cho mét nhÞ thøc (x - x_i) ta ®−îc :

P_n(x) = (x - x_i)P_n-1(x) + b_n

víi b_n= P_n(x_i).§a thøc P_n-1(x) cã d¹ng :

P_n-1(x) = b_ox^n-1+ b₁x^n-2+p₃x^n-3+..+ b_n-2x + b_n-1

(4)

thøc cÇn t×m nghiÖm P_n(x) mµ c¸c hÖ sè a_i®· cho:

(x - x_i)( b_ox^n-1+ b₁x^n-2+b₃x^n-3+..+ b_n-2x + b_n-1) + b_n

= a_oxⁿ+ a₁x^n-1+ a₂x^n-2+...+ a_n-1x + a_n

(5)

Tõ (5) rót ra :

b_o= a_o

b₁= a₁+ b_ox_i

b₂= a₂+ b₁x_i

......

(6)

b_k= a_k+ b_k-1x_i

.......

101

b_n= a_n+ b_n-1x_i= P_n(x_i)

§¹o hµm (3) ta ®−îc :

′

P_n(x) = (x − x_i)P_n−1(x) + P_n−1(x)

vµ

′

P_n(x_i) = P_n−1(x_i)

(7)

Nh− vËy víi mét gi¸ trÞ x_inµo ®ã theo (2) ta tÝnh ®−îc P_n(x_i) vµ kÕt hîp (6) víi (7)

tÝnh ®−îc P′_n(x_i).Thay c¸c kÕt qu¶ nµy vµo (1) ta tÝnh ®−îc gi¸ trÞ x_i+1.Qu¸ tr×nh ®−îc tiÕp tôc

cho ®Õn khi | x_i+1- x_i| < ε hay P_n(x_i+1) ≈ 0 nªn α₁≈ x_i+1lµ mét nghiÖm cña ®a thøc.

PhÐp chia P_n(x) cho (x - α₁) cho ta P_n-1(x) vµ mét nghiÖm míi kh¸c ®−îc t×m theo

c¸ch trªn khi chän mét gi¸ trÞ x_omíi hay chän chÝnh x_o= α₁.Khi bËc cña ®a thøc gi¶m

xuèng cßn b»ng 2 ta dïng c¸c c«ng thøc t×m nghiÖm cña tam thøc ®Ó t×m c¸c nghiÖm cßn

l¹i.

VÝ dô:t×m nghiÖm cña ®a thøc P₃(x) = x³- x²-16x + 24

a_o= 1

a₁= -1

a₂= -16

a₃= 24

Chän x_o= 3.5 ta cã :

P_o= a_o= 1

P₁= a₁+ p_ox₀= -1 + 3.5*1 = 2.5

P₂= a₂+ p₁x₀= -16 + 3.5*2.5 = -7.25

P₃= a₃+ p₂x₀= 24 + 3.5*(-7.25) = - 1.375

b₀= a₀= 1;

b₁= a₁+ b_ox₀= -1 + 3.5*1 = 2.5

b₂= a₂+ b₁x₀= -16 + 3.5*2.5 = -7.25

P₂(3.5) = b₀x²+ b₁x + b₂= 13.75

P_n(x₀)

1.375

13.75

x₁= x₀−

= 3.5 +

= 3.6

′

P_n(x₀)

LÆp l¹i b−íc tÝnh trªn cho x₁ta cã:

P_o= a_o= 1

P₁= a₁+ p_ox₁= -1 + 3.6*1 = 2.6

P₂= a₂+ p₁x₁= -16 + 3.6*2.6 = -6.64

P₃= a₃+ p₂x₁= 24 + 3.6*(-6.64) = - 0.096

b_o= a_o= 1

b₁= a₁+ b_ox₁= -1 + 3.6*1 = 2.6

b₂= a₂+ p₁x₁= -16 + 3.6*2.6 = -6.64

P₂(3.6) = b₀x²+ b₁x + b₂= 15.68

P_n(x₁)

0.096

15.68

x₂= x₁−

= 3.6 +

= 3.606

′

P_n(x₁)

thuËt tÝnh trªn.

Ch−¬ng tr×nh 8-8

//phuong phap Birge-Viette

#include <conio.h>

#include <stdio.h>

#include <math.h>

#define max 20

102

void main()

{

float a[max],p[max],d[max],x[max];

int k,j,i,n;

float e1,e2,x0,x1;

clrscr();

printf("Cho bac cua da thuc n = ");

scanf("%d",&n);

e1=0.0001;

printf("Cho cac he so cua da thuc can tim nghiem\n");

for (i=0;i<=n;i++)

{

printf("a[%d] = ",i);

scanf("%f",&a[i]);

}

x0=a[0];

for (i=0;i<=n;i++)

a[i]=a[i]/x0;

printf("Nghiem cua phuong trinh : \n");

tt:x0=-a[n]/a[n-1];

j=0;

do

{

j=j+1;

p[1]=x0+a[1];

d[1]=1.0;

for (k=2;k<=n;k++)

{

p[k]=p[k-1]*x0+a[k];

d[k]=d[k-1]*x0+p[k-1];

}

x1=x0-p[n]/d[n];

e2=fabs(x1-x0);

if (e2>e1)

x0=x1;

}

while((j<=50)||(e2>=e1));

if (e2>=e1)

printf("Khong hoi tu");

else

printf(" x = %.4f\n",x1);

n=n-1;

if (n!=0)

{

for (k=1;k<=n;k++)

a[k]=p[k];

goto tt;

}

103

getch();

}

Dïng ch−¬ng tr×nh trªn ®Ó t×m nghiÖm cña ®a thøc x⁴+ 2x³- 13x²- 14x + 24 ta ®−îc

c¸c nghiÖm lµ:-4 ; 3 ; -2 vµ 1.

§9.Ph−¬ng ph¸p ngo¹i suy Aitken

XÐt ph−¬ng ph¸p lÆp :

x = f(x)

(1)

víi f(x) tho¶ m·n ®iÒu kiÖn héi tô cña phÐp lÆp,nghÜa lµ víi mäi x∈ [a,b] ta cã :

| f’(x) | ≤ q < 1

Nh− vËy :

(2)

x_n+1= f(x_n)

x_n= f(x_n-1)

(3)

(4)

Trõ (3) cho (4) vµ ¸p dông ®Þnh lÝ Lagrange cho vÕ ph¶i víi c ∈ [a,b] ta cã :

x_n+1- x_n= f(x_n) - f(x_n-1) = (x_n- x_n-1)f’(c)

V× phÐp lÆp (1) nªn :

(5)

(6)

| x_n+1- x_n| ≤ q | x_n- x_n-1|

104

Do (6) ®óng víi mäi n nªn cho n = 1 , 2 , 3 , . . . ta cã :

| x₂- x₁| ≤ q | x₁- x_o|

| x₃- x₂| ≤ q | x₂- x₁|

. . . . . . . . . . . . . . . . . . .

| x_n+1- x_n| ≤ q | x_n- x_n-1|

q . Nh− vËy :

x_n+1− y

x_n− y

= q < 1

(7)

hay :

x_n+1− y = q(x_n− y)

x_n+2− y = q(x_n+1− y)

(8)

(9)

T−¬ng tù ta cã :

Tõ (8) vµ (9) ta cã :

x_n+2− x_n+1

q =

(10)

(11)

x_n+1− x_n

Thay gi¸ trÞ cña q võa tÝnh ë (10) vµo biÓu thøc cña q ë trªn ta cã :

2

(

)

x_n− x_n+1

x_n− 2x_n+1+ x_n+1

y = x_n−

C«ng thøc (11) ®−îc gäi lµ c«ng thøc ngo¹i suy Adam.Nh− vËy theo (11) tr−íc hÕt ta dïng

ph−¬ng ph¸p lÆp ®Ó tÝnh gi¸ trÞ gÇn ®óng x_n+2,x_n+1,x_ncña nghiÖm vµ sau ®ã theo (11) t×m

®−îc nghiÖm víi sai sè nhá h¬n.

§Ó lµm vÝ dô chóng ta xÐt ph−¬ng tr×nh :

lnx - x²+ 3 = 0

Ta ®−a vÒ d¹ng lÆp :

x = ln(x) + 3

1

′

f (x) =

2x lnx + 3

PhÐp lÆp héi tô trong ®o¹n [0.3,∝].Ta cho x₁= 1 th× tÝnh ®−îc :

x₂= 1,7320508076

x₃= 1.883960229

x₄= 1.90614167

y = 1.909934347

§Ó gi¶m sai sè ta cã thÓ lÆp nhiÒu lÇn

Ch−¬ng tr×nh 8-9

//phuong phap Aitken

#include <conio.h>

#include <stdio.h>

#include <math.h>

#define m 5

void main()

{

float x[m];

105

float epsi,n,y;

int i,z;

float f(float);

clrscr();

printf("Cho tri so ban dau x[1] = ");

scanf("%f",&x[1]);

printf("Cho tri so sai so epsilon = ");

scanf("%f",&epsi);

printf("\n");

printf( "Ngoai suy Aitken cua ham\n");

z=0;

while (z<=20)

{

for (i=2;i<=4;i++)

x[i]=f(x[i-1]);

n=x[4]-2*x[3]+x[2];

if ((fabs(n)<1e-09)||(fabs(x[1]-x[2])<epsi*fabs(x[1])))

z=20;

else

{

y=x[2]-(x[3]-x[2])*(x[3]-x[2])/n;

if (z>20)

printf("Khong hoi tu sau hai muoi lan lap\n");

x[1]=y;

}

z=z+1;

}

printf("Nghiem cua phuong trinh y = %.6f",y);

getch();

}

float f(float x)

{

float s=sqrt(log(x)+3);

return(s);

}

Víi gi¸ trÞ ban ®Çu lµ 1 vµ sai sè lµ 1e-8,ch−¬ng tr×nh cho kÕt qu¶ y = 1.9096975944

§10.Ph−¬ng ph¸p Bairstow

Nguyªn t¾c cña ph−¬ng ph¸p Bairstow lµ trÝch tõ ®a thøc P_n(x) mét tam thøc Q₂(x) =

x²- sx + p mµ ta cã thÓ tÝnh nghiÖm thùc hay nghiÖm phøc cña nã mét c¸ch ®¬n gi¶n b»ng

c¸c ph−¬ng ph¸p ®· biÕt.

ViÖc chia ®a thøc P_n(x) cho tam thøc Q₂(x) ®−a tíi kÕt qu¶ :

P_n(x) = Q₂(x).P_n-2(x) + R₁(x)

víi

P_n(x) = a_oxⁿ+ a₁x^n-1+ a₂x^n-2+...+ a_n

Q₂(x) = x²- sx + p

106