Смекни!
smekni.com

записка с., 4 табл., 2 приложения, 5 источников (стр. 8 из 8)

Ограничения использования: многочлен

должен удовлетворять условию теоремы Штурма.

Область применения: решение задач связанных с определением числа действительных корней многочлена, принадлежащих некоторому интервалу (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