- •1. Операции над полиномами
- •1.1 Умножение полиномов
- •2. Нахождение корней полинома
- •2.1 Предварительный анализ функции
- •2.1.1 Метод секущих (метод хорд)
- •2.1.2 Метод касательных
- •2.2 Итерационные методы поиска корней полинома.
- •2.2.1 Метод Ньютона
- •2.2.3 Метод Бэрстоу
- •2.2.2 Метод Лина
- •Составление процедуры по методу Бэрстоу на Pascal.
Составление процедуры по методу Бэрстоу на Pascal.
В процедуре bairstow итерация Берстоу используется для последовательного нахождения пар корней полиномиального уравнения степени n с коэффициентами а[i] (i=0,1,...,п), где a[n]—свободный член.
Выходные параметры:
num— число пар найденных корней (num — начальные буквы слова number—число);
x[i], y[i] (i=1, 2,..., num)—пара действительных корней, если nat[i]=1 (nat — начальные буквы слова natural — естественный), или действительная и мнимая части комплексной пары, если nat[i]=—1;
ex[i] указывает, по какому из следующих четырех условий произошел выход (ех— начальные буквы слова exit — выход) из итерационного цикла при нахождении пары корней x[i], y[i];
ex[i]=1, если u0 и u1 стали по модулю меньше eps1;
ex[i]=2, если поправки corp, corq (cor — начальные буквы слова correction — поправка) становятся по модулю меньше eps2;
ex[i] =3, если отношения corp/p, corq/q становятся меньше eps3;
ex[i] =4, если число итераций становится равным max. В последнем случае найденная пара корней недостоверна. При этом не делается никакой попытки найти остальные корни. eps0 используется как нижняя граница знаменателя (det) в выражениях, из которых были найдены corp и corq.
Входные массивы х, у, nat и ех должны иметь размерность [1:(n+1):2].
procedure bairstow(n,a,eps0,epsl,eps2,eps3,max)
result: (num,x,y,nat,ex);
value eps0,epsl,eps2,eps3,n,max;
real eps0,epsl,eps2,eps3;
integer n,max,num;
array a,x,y;
integer array nat,ex;
begin real p,q,corp,corq,u0,ul,v0,vl,w0,wl,det,s,t;
integer i,j,k,m,n2,r;
array b,cf0[n + l];
for i:= 0 step 1 until n do b[i]: = a[i];
b[n+l]:=0;
n2:= (n + 1):2;
r:=2*n2;
for m:= 1 step 1 until n2 do begin p: = q:=0;
for k: = 1 step 1 until max do
labl: begin
for i:= 0 step 1 until r do c[i]:=b[i];
for i:= r—2,г—4 do
for j:=0 step 1 until i do begin c[j +1]:=c[j + l]-p*c[j];
c[j + 2]:==c[j+2]—q*c[j] end
u0: = c[r];
ul: = c[r—1];
v0:—c[r—2];
vl: = c[r—3];
w0:=—q*vl;
wl:=v0—p*vl;
det:=v0*wl—w0*vl;
if abs (det) < eps0 then begin p: = p + l;
q:=q+l;
go to labl end;
corp:= (v0*ul—u0*vl)/det;
corq:= (u0*wl—w0*ul)/det;
p: = p+corp;
q: = q+corq;
If (abs(u0) <epsl) /\ (abs(ul) <epsl)then
begin ex[m]: = l;
go to lab2 end;
If(abs(corp) <eps2) /\ (abs(corq) <eps2) then
begin ex[m]:=2;
go to lab2 end;
If (abs(corp) <eps3*abs(p)) /\ (abs(corq) <eps3*abs(q)) then begin ex[m]:=3;
go to lab2 end
end k;
ex[m]:—4;
lab2: s:=—p/2;
t:=s*s—q;
if t^0 then
begin nat[m]: = l; t: = sqrt(t);
x[m]: = s+t;
y[m]:=s—t end else
begin nat[m]: =—1;
x[m]:=s;
y[m]:=sqrt(—t) end;
if ex[m]=4 then go to out;
r:=r—2;
for j:=0 step 1 until r do
begin b[j +1]:=b[j +1]—p*b[j];
b[j+2]:=[b0+2]-q*b0] end;
If r< 1 then but: begin num:=m;
go to fin end;
if r<3 then begin m:=m + l;
ex[m]: = l;
p:=b[l]/b[0];
q:=b[2]/b[0];
go to lab2 end end m;
fin: end bairstow;
Рагинис Дмитрий из группы 1961.
Здравствуйте, Дмитрий
Спасибо!
Однако!!!
где тестовые примеры
для построения (ВЫЧИСЛЕНИЯ!!!) комплексных корней
и графики сходимости итерационных процессов и для вещественных корней
и для комплексных
по Ньютону Лину Бэрстоу
С уважением,
Александр Сергеевич.
Список используемых источников:
1. Агеев М.И.Библиотека алгоритмов.1978
2. Шуп Т.Е. Прикладные численные методы в физике и технике. 1990
http://ru.wikipedia.org/wiki/ Википедия
От кого:
Рагинис Дмитрий из группы 1961.
RaiTeck <agresiff@rambler.ru>
в адресную книгу•в чёрный список•в фильтры
Кому:Слюсаренко Александр Сергеевич <sas_2000@mail.ru>
Дата:Ср 20 июл 2011 00:43:09
Тема:Реферат Полиномы
-
