PHƯƠNG PHÁP LẶP BIRGE - VIETTE

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   

                                                          

                                                                                                    (1)

Để 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_o nào đó, ví dụ :

                                                                                  

và tính tiếp các giá trị sau :                           

                                                    

Tiếp theo có thể đánh giá P_n(x_i) theo thuật toán Horner :

P₀ = a₀

                P₁= P₀x_i + a₁                                                                                                                                         (2)

                P₂= P₁x_i + a₂

                P₃= P₂x_i + a₃

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

                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                                                                                                   (3)

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)

Để xác định các hệ số của đa thức (4) ta thay (4) vào (3) và cân bằng các hệ số với đa thức cần tìm nghiệm P_n(x) mà các hệ số ai đã 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ⁿ_-1x + a=                                                                                             (5)

Từ (5) rút ra :

b_o = a_o

b₁ = a₁ + b_ox_i                                                                                                                                         (6)

                b₂= a₂ + b₁x_i

                        ......

                b_k= a_k + b_k-1x_i

                .......

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

                Đạo hàm (3) ta được :

               

và:                                               

                                                                                               (7)

                Như vậy với một giá trị x_i nà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 | < e hay P_n(x_i+1) » 0 nên a₁ » x_i+1là một nghiệm của đa thức.

                Phép chia P_n(x_­) cho (x -  a₁) 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=a₁. 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

ao_­ = 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

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

Quá trình cứ thế tiếp tục cho đến khi sai số chấp nhận được. Chương trình dưới đây mô tả thuật tính trên.

 

Chương trình 2-8

//phuong phap Birge-Viette

#include <conio.h>

#include <stdio.h>

#include <math.h>

#define  max  20

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;

                  }

                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.