Ограничения использования: многочлен
должен удовлетворять условию теоремы Штурма.Область применения: решение задач связанных с определением числа действительных корней многочлена, принадлежащих некоторому интервалу (a,b).
Листинг программы представлен в Приложении А.
2.3.2 Программа MLG
Программа MLG предназначена для приближенного нахождения корней уравнения 4-го порядка методом Лобачевского–Греффе.
Входные данные: коэффициенты многочлена, корни которого необходимо найти.
Выходные данные: коэффициенты всех вспомогательных полиномов, полученных в ходе квадрирования исходного многочлена, корни уравнения полученные с заданной точностью, оценка относительной условной погрешности найденных корней.
Ограничение использования: количество комплексно–сопряженных корней должно быть не менее двух. При слабой начальной отделенности корней, рекомендуется использовать другие методы решения.
Область применения: задачи связанные с нахождением всех корней заданного многочлена 4-го порядка. С незначительными изменениями программу можно использовать для решения уравнений методом Лобачевского–Греффе любого порядка.
Листинг программы приводится в Приложении В к данному курсовому проекту.
2.4 Анализ полученных результатов
Из полученных при решении уравнений (2.1) и (2.4) уравнений можно судить о следующих особенностях метода Лобачевского–Греффе.
С помощью рассматриваемого метода можно найти все корни многочлена с достаточно высокой точностью, при не большом количестве итераций.
Величина погрешности полученных корней в высокой степени зависит от отделенности корней в исходном многочлене, так, например, в уравнении (2.1) минимальная разность между различными по модулю корнями равна
и в уравнении (2.4), что в результате дает погрешности разных порядков (4.52958089E–11 и 4.22229789E-06 соответственно) при одинаковом количестве итераций.Таким образом, метод Лобачевского–Греффе дает хорошую точность при отделенных корнях, и значительно теряет при кратных или близких по модулю корнях.
Метод Лобачевского–Греффе, который был рассмотрен в данном курсовом проекте, имеет простую схему вычислений и позволяет с помощью небольших по объему вычислений найти с большой точностью модулю всех корней алгебраического уравнения, исключая разве только кратные или очень близкие по модулю корни. Однако окончательное нахождение корней требует значительной вычислительной работы, особенно в случае комплексных корней.
Затруднительным для метода является нахождение кратных корней. Однако метод можно применять и в этом случае, если предварительно избавиться от кратных корней с помощью алгоритма, описанного в данной работе.
Наибольшую проблему представляют корни близкие по модулю, т. к. в этом случае происходит большая потеря точности вычислений, что влечет за собой необходимость в увеличении затрат ресурсов. В данном случае рекомендуется пользоваться другими методами нахождения корней алгебраического уравнения.
Метод Лобачевского–Греффе один из самых эффективных методов вычислений, который при небольшом количестве итераций дает результат с довольно хорошей точностью, поэтому сфера использования этого метода на практике очень широкая. Методом можно пользоваться при построении математических моделей химических и физических процессов, в методах оптимизации.
1. В.П. Демидович, И.А. Марон. Основы вычислительной математики.– М.: Наука, 1966.–664с.
2. В.Л. Загускин. Справочник по численным методам решения алгебраических и трансцендентных уравнений.– М.: Государственное издательство физико-математической литературы, 1960.–216с.
3. В.И. Крылов, В.В. Бобков, П.И. Монастырский. Вычислительные методы высшей математики.–Минск: Вышэйшая школа, 1972, т. 1.–584с.
4. А.Г. Курош. Курс высшей алгебры.–М.: Наука,1971,–432с.
5. Ю.И. Рыжиков. Программирование на Фортране PowerStation для инженеров. Практическое руководство.–СПб.: КОРОНА принт, 1999.–160с.
Листинг программы Sturm. Применяется для построения системы Штурма.
! Sturm.f90
!
!************************************************************************
!
! PROGRAM: Sturm
!
! PURPOSE: Построение системы Штурма.
!
!************************************************************************
program Sturm
implicit none
double precision, dimension(1:5,0:4) ::a
double precision, dimension(0:4) ::c
double precision, dimension(0:4,0:4) ::maxmas
integer i,j,l
double precision a1
print *,'vvedite koeffitsienty mnogochlena', ' '
read *, c !чтение данных
a(1,0:4) = c
!вычисление производной
do i=0,3
a(2,i)=a(1,i)*(4-i)
end do
a1 = abs(a(2,0))
do i=0,3
a(2,i) = a(2,i)/a1
end do
print '(en13.3)',a(2,0:3)
! вычисление первого частного
a(3,0:4) = a(1,0:4)
do i=0,1
a1 = a(3,i)/a(2,0)
do j=0,3
a(3,j+i) = a(3,j+i)-a1*a(2,j)
end do
end do
a(3,0:2) = a(3,2:4)
a(3,3:4) = 0
a1 = abs(a(3,0))
do i=0,2
a(3,i) = a(3,i)/a1
end do
a(4,0:4) = a(2,0:4)
print *,' '
print '(en13.3)',a(3,0:2)
! вычисление второго частного
do i=0,1
a1 = a(4,i)/a(3,0)
do j=0,3
a(4,j+i) = a(4,j+i)-a1*a(3,j)
end do
end do
a(4,0:2) = a(4,2:4)
a(4,3:4) = 0
a1 = abs(a(4,0))
do i=0,2
a(4,i) = a(4,i)/a1
end do
a(5,0:4) = a(3,0:4)
print *,' '
print '(en13.3)',a(4,0:1)
! вычисление третьего частного
do i=0,1
a1 = a(5,i)/a(4,0)
do j=0,3
a(5,j+i) = a(5,j+i)-a1*a(4,j)
end do
end do
a(5,0:2) = a(5,2:4)
a(5,3:4) = 0
print *,' '
print '(en13.3)',a(5,0)
end program Sturm
Программа MLG. Решение алгебраического уравнения.
! MLG.f90
!
!***********************************************************************
!
! PROGRAM: MLG
!
! PURPOSE: Решение алгебраического уравнения методом Лобачевского-Греффе
!
!***********************************************************************
program MLG
implicit none
double precision, dimension(0:4) ::a1,b2,eps,summa
double precision, dimension(0:8) ::b1
double precision, dimension(1:4) ::y,lg,dx
double precision, dimension(1:3) ::b3
double precision koef,v,sumcmplx,prcmplx,e1,e2, epsilon
double complex deskr
double complex, dimension(1:4) ::x
logical, dimension(0:4) ::mask
logical, dimension(1:4) ::flags
logical flag
integer i,k,m
! задание начальных значений
epsilon = 1e-3
print *,'vvedite koeffitsienty mnogochlena', ' '
read *, a1 !чтение данных
!открытие файла для записи данных
open (3, file='res2.txt', status='replace')
write (3,10) a1
10 format (t3,'коэффициенты исходного многочлена',5(2x,es15.7))
write (3,11) epsilon
11 format (t3,'ограничение точности ',es15.7)
y = 0.0
mask = .true.
b1 = 0.0
b1(0:4) = a1
flag = .true.
k=0
!операция квадрирования корней
do while (flag)
k = k + 1 !считаем номер итерации
write (3,1) k
1 format (t60,'итерация № ',t75,i2)
b2 = b1(0:4)*b1(0:4)
summa = (/(2*s(i),i=0,4)/)
write (3,2) summa
2 format (t3,'удвоенная сумма',5(2x,es15.7))
print *,' '
b2 = (/(b2(i)+2*s(i),i=0,4)/) !вычисление коэффициентов
write (3,3) b2
3 format (t3,'коэффициенты ',5(2x,es15.7))
mask = mask .and. (b2 > 0) !определение действительных корней
eps = 0.0
where (mask) eps = abs(b2/(b1(0:4)*b1(0:4))-1)
flag = maxval(eps)>epsilon !ограничение точности
if (.not. flag) then
k = k-1
do i=1,4
if (.not. mask(i)) then
e1 = abs(b2(i-1) - b1(i-1)*b1(i-1))
e2 = abs(b2(i+1) - b1(i+1)*b1(i+1))
koef = 1/exp((k+1)*LOG(2.0))
dx(i) = koef*(e1/(b1(i-1)*b1(i-1))+e2/(b1(i+1)*b1(i+1)))
else
e1 = abs(b2(i-1) - b1(i-1)*b1(i-1))
e2 = abs(b2(i) - b1(i)*b1(i))
koef = 1/exp((k+1)*LOG(2.0))
dx(i) = koef*(e1/(b1(i-1)*b1(i-1))+e2/(b1(i)*b1(i)))
end if
end do
else
b1(0:4) = b2 !запоминаем значение коэффициентов на текущей итерации
end if
write (3,4)
4 format (t3,' ')
end do
!определение номеров комплексных корней
do i=1,4
if (.not. mask(i)) m=i
end do
mask(m+1) = .false.
dx(m+1) = dx(m)
!вычисление корней в уравнении Q(y) = 0
do i=1,4
if (mask(i)) y(i) = b1(i)/b1(i-1)
end do
!вычисление действительных корней
koef = 1/exp(k*LOG(2.0))
where (mask(1:4)) lg = exp(koef*log(y))
!определение знака действительных корней
flags = .false.
do i=1,4
if (mask(i)) then
v = polinom(lg(i))/polinom(-1.0*lg(i))
flags(i) = (v > 1.0)
end if
end do
where (flags) lg = -1.0*lg
x = lg
!составляем уравнение для нахождения комплексных корней
sumcmplx = -a1(1)/a1(0)
do i=1,4
if (mask(i)) then
sumcmplx = sumcmplx - x(i)
end if
end do
v = -1.0
prcmplx = extent_int(v,4)*a1(4)/a1(0)
do i=1,4
if (mask(i)) then
prcmplx = prcmplx/x(i)
end if
end do
b3(1) = 1.0
b3(2) = -1.0*sumcmplx
b3(3) = prcmplx
!нахождение комплексных корней
v = b3(2)*b3(2)-4*b3(1)*b3(3)
deskr = dcmplx(-1.0*b3(2),sqrt(abs(v)))/(2*b3(1))
x(m) = deskr
x(m+1) = CONJG(x(m))
!вывод результата
write (3,5)
5 format (t3,'-------------------------------------')
write (3,6)
6 format (t3,'полученый результат')
do i=1,4
write (3,7) x(i)
7 format (t20,2(es15.8,3x))
write (3,8)
8 format (t3,'')
end do
write (3,9) dx
9 format (t3,'относительная погрешность корней ',4(es15.8,2x))
print *,'vse vychisleniya vypolneny uspeshno', ' ', 'rezultat sohranen v faile res2.txt'
close (3, status='keep')
contains
real(8) function s(a)
integer a,j
real(8) sum
sum = 0.0
do j=1,a
if (mod(j,2) == 0) then
sum = sum + b1(a-j)*b1(a+j)
else
sum = sum - b1(a-j)*b1(a+j)
end if
end do
s=sum
end function s
real(8) function polinom(xp)
real(8) xp,p,xs
integer j,l
p = 0.0
do j=0,4
p = p+ extent_int(xp,j)*a1(4-j)
end do
polinom = p
end function polinom
real(8) function extent_int(num,ext)
real(8) num
integer ext,l
real(8) w
w=1.0
do l=1,ext
w = w*num
end do
extent_int = w
end function extent_int
end program MLG