Реферат: НАХОЖДЕНИЕ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ КОРНЕЙ АЛГЕБРАИЧЕСКОГО МНОГОЧЛЕНА МЕТОДОМ ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ (БИСЕКЦИИ) И МЕТОДОМ ХОРД И КАСАТЕЛЬНЫХ С УКАЗАННОЙ ТОЧНОСТЬЮ И УЧЕТОМ ВОЗМОЖНОЙ КРАТНОСТИ КОРНЕЙ
а границу отрицательных корней – заменив в уравнении (1) х на –х.
Таким образом, мы получаем метод, хотя и достаточно медленный (впрочем, при неудачном выборе нулевого приближения в методе итераций поиск решения может затянуться на еще более долгое время, да и к тому же неизвестно, приведет ли весь ход вычислений к ответу), но зато вполне надежный и простой метод, не требующий решения дополнительных задач, вроде вычисления производной, а рекурсивность самого алгоритма позволяет получить очень компактный и легко читаемый код. Именно поэтому метод половинного деления и был выбран для реализации на программном уровне.
2.2.4. Метод разложения на множители
Данный метод является полностью аналитическим, однако полностью зависим от других. Главным его преимуществом является то, что в данном методе не происходит потери кратных корней. Поясним на примере:
Пусть дан многочлен F(x) = 2x3-11x2+20x-12 (11)
Его можно записать в виде: F(x) = (x+2)2(2x-3) (12)
У многочлена n-степени, как известно, n корней, а из (12) следует, что корнями F(x) являются –2 и 1,5, причем корень –2 является кратным, т.е. фактически это два одинаковых корня. При отыскании же корней любым из вышеописанных методов «второй» корень –2 будет потерян, т.к. график функции будет иметь лишь две точки пересечения с осью абсцисс
Чтобы избежать этого применяется метод разложения на множители. Суть его заключается в следующем: каждый многочлен вида (1) можно представить в виде (x+h1)(x+h2)…(x+hn)*H = 0 (13) ,
или F(x) = (x+h)(bn-1xn-1+…b1)+b0 (14)
где h1…hn – корни уравнения, а Н – произведение множителей х, вынесенных за скобки ( Н никак не влияет на уравнение, т.к. от него избавляются, деля на Н обе части (13). При этом не исключено, что некоторые h могут быть взаимно равны, что и свидетельствует о наличии кратного корня.
Для вычисления значений новых коэффициентов в (14) используются формулы:
bn=an
bn-1=bnh+an-1 (15)
bn-2=bn-1h+an-2
…
Таким образом, алгоритм этого метода выглядит следующим образом:
1. Определить границы корней уравнения;
2. При помощи любого из вышеописанных методов найти один корень уравнения;
3. Применяя формулы (14) и (15) сформировать новый многочлен степени, на 1 меньшей предыдущего.
4. Вернуться к пункту 2.
5. Повторять до тех пор, пока степень многочлена не обнулится.
Этот метод был реализован на программном уровне и включен в курсовую работу.
3. ОПИСАНИЕ СТРУКТУРЫ ПРОГРАММЫ
В рамках задания на курсовую работу в среде программирования Visual Basic for Applications была разработана программа, находящая корни многочлена с указываемой точностью.
3.1. Описание программных модулей
Разработка программы велась с учетом концепции объектно-ориентированного программирования, поэтому четко определенной последовательности действий в ней нет. Однако, разбирая программу на составляющие, можно проследить «путь» алгоритма в коде.
Вся программа состоит из форм и модулей. Модулей всего два: один содержит стандартную процедуру автозапуска (его рассматривать мы не станем), а другой – все «публичные» процедуры и функции.
Public function F(x). Функция, возвращающая значение многочлена для передаваемого х.
Public function DetectBorders. Возвращает границы корней, согласно формулам ( 7 , 8, 9 ).
Public sub Gra – процедура, «ответственная» за составление графика.
3.2. Описание форм
В формах заключена основная часть программы, в том числе и собственно алгоритм метода половинного деления. Решение «упаковать» эти функции в формы было продиктовано следующими причинами:
- сокращение объема занимаемой памяти и, как следствие, ускорение работы за счет сокращения времени жизни переменных;
- разграничение доступа (т.е. необходимая функция или метод могут быть активированы исключительно в допустимой ситуации – это значительно снижает вероятность ошибок);
- каждая форма является «вещью в себе» и не зависит от остальных (кроме «корневой»
3.2.1. Форма Form_Main
Является корневой формой программы, содержит Главное меню, позволяющее в любом порядке выполнять все необходимые действия, а также сохранять и завершать работу программы.
3.2.2. Форма Form_Koeff
В этой форме задаются коэффициенты многочлена.
Замечание. Для задания коэффициента а0 необходимо указать значение степени х равным 0.
3.2.3.Форма Form_Mnogo
 |
Выводит на экран общий вид заданного многочлена, а также производных первого и второго порядков
3.2.4.Форма Form_WP
Эта форма по существу является панелью управления в режиме графика и позволяет его распечатать или закрыть.
3.2.5. Форма Form_Korni
«Основная форма» – именно в ней заключен сам алгоритм поиска корней (Sub FindKor) методами бисекции и хорд/касательных.
В качестве свойств в объекте «форма» присутствуют три ключевые процедуры, реализующие собственно алгоритмы нахождения корней и нахождения производной.
Public sub FF* – процедура, «ответственная» за нахождение производной.
Public sub Horda_Kasatelnye – процедура, реализующая поиск корней по алгоритму хорд и касательных.
Public sub Find_Kor – процедура, реализующая поиск корней по алгоритму половинного деления отрезка.
Замечание. Алгоритмы нахождения крней описаны в главе 2. Суть же алгоритма нахождения производной сводится к простому перемножению коэффициента и степени и уменьшению значения степени на единицу. Это позволяет корректно определить производную, при этом корректно «избавиться» от конечной константы.
4. АНАЛИЗ РЕЗУЛЬТАТОВ
В результате выполнения задания на курсовую работу была создана программа VI Function 2.0 , находящая корни алгебраического многочлена вида (1) с указываемой точностью посредством следующих методов:
· метод деления отрезка пополам;
· метод хорд и касательных (комбинированный)
Также при составлении программы была учтена возможность наличия у многочлена кратных корней, и средства их обнаружения также вошли в состав программы.
Фактические результаты совпали с формальными.
5. СПИСОК ЛИТЕРАТУРЫ
1. Гутер Р.С. , Овчинский Б.В. «Элементы численного анализа и математический обработки результатов опыта». Москва, «Наука», 1979
2. Калиткин Н.Н. «Численные методы». Москва, «Наука», 1978
3. Крылов В.И., БабковВ.В., Монастырский П.И. «Вычислительные методы». Москва, «Наука», 1976
4. П. Санна. «Visual Basic for Applications 6.0 «в подлиннике», Киев, BHV
6. ПРИЛОЖЕНИЯ
6.1. Пример алгебраического многочлена и нахождения его
корней
Многочлен F(x) = 3x2+5x-8
График представлен на рис. 6.1
Точность Q = 0,0001
Найденные корни x = -2,66666669921875 метод
x=
0,99991015625 бисекции
Найденные корни x = -2,66667654214111 метод
x= 0,99981915025 хорд и касательных
рис. 6.1
6.2. Блок-схема алгоритма половинного деления
A = левая граница
В = правая граница
C – середина
F(x) - функция
6.3. Блок-схема алгоритма поиска корней методом хорд и касательных
A = левая граница
В = правая граница
F(x) - функция
6.4 Руководство пользователя.
После запуска программы перед Вами появится Главное меню, включающее в себя следующие пиктограммы:
СОХРАНИТЬ |
Сохраняет файл со всеми сделанными изменениями |
|
ПРОСМОТР ФУНКЦИИ |
Выводит на экран окно, в котором отображается вид многочлена, а также вид производных первого и второго порядков (Выбор осужествляется нажатием кнопок F’(X), F”(X), F(X) |
|
ВВОД КОЭФФИЦИЕНТОВ |
Выводит на экран окно ввода коэффициентов |
|
ГРАФИК |
Выводит график функции |
|
ПОИСК КОРНЕЙ |
Отображает окно, управляющее поиском корней |
|
О ПРОГРАММЕ |
Выводит окно «О программе» |
|
ВЫХОД |
Завершает работу програмы, предварительнозадавая вопрос о сохранении изменений |
Ввод коэффициентов осуществляется следующим образом: в появившемся окне имеются 2 поля – одно для указания степени, другое для ввода собственно коэффициента. Если Вы уже вводили некоторую функцию, то для ее удаления нажмите кнопку “очистить”, для запоминания коэффициента нажмите “Ок”, для завершеня ввода – “завершить”.
Поиск корней упрощен до предела. Вам достаточно указать неоюходимую точность и выбрать метод поиска: бисекционый или комбинированный.
6.5. Исходный текст программы
UNIT1
Dim curcell As Range
Dim ma As Double
Dim Ao As Double
Public Function F(x As Variant)
F = (x ^ 20 * Range("a20").Value) + (x ^ 19 * Range("a19").Value) + (x ^ 18 * Range("a18").Value) + (x ^ 17 * Range("a17").Value) + (x ^ 16 * Range("a16").Value) + (x ^ 15 * Range("a15").Value) + (x ^ 14 * Range("a14").Value) + (x ^ 13 * Range("a13").Value) + (x ^ 12 * Range("a12").Value) + (x ^ 11 * Range("a11").Value) + (x ^ 10 * Range("a10").Value) + (x ^ 9 * Range("a9").Value) + (x ^ 8 * Range("a8").Value) + (x ^ 7 * Range("a7").Value) + (x ^ 6 * Range("a6").Value) + (x ^ 5 * Range("a5").Value) + (x ^ 4 * Range("a4").Value) + (x ^ 3 * Range("a3").Value) + (x ^ 2 * Range("a2").Value) + (x * Range("a1").Value) + Range("a21").Value
End Function
Public Function F1(x As Variant)
F1 = (x ^ 20 * Range("j20").Value) + (x ^ 19 * Range("j19").Value) + (x ^ 18 * Range("j18").Value) + (x ^ 17 * Range("j17").Value) + (x ^ 16 * Range("j16").Value) + (x ^ 15 * Range("j15").Value) + (x ^ 14 * Range("j14").Value) + (x ^ 13 * Range("j13").Value) + (x ^ 12 * Range("j12").Value) + (x ^ 11 * Range("j11").Value) + (x ^ 10 * Range("j10").Value) + (x ^ 9 * Range("j9").Value) + (x ^ 8 * Range("j8").Value) + (x ^ 7 * Range("j7").Value) + (x ^ 6 * Range("j6").Value) + (x ^ 5 * Range("j5").Value) + (x ^ 4 * Range("j4").Value) + (x ^ 3 * Range("j3").Value) + (x ^ 2 * Range("j2").Value) + (x * Range("j1").Value) + Range("j21").Value
End Function
Public Function F2(x As Variant)
F2 = (x ^ 20 * Range("m20").Value) + (x ^ 19 * Range("m19").Value) + (x ^ 18 * Range("m18").Value) + (x ^ 17 * Range("m17").Value) + (x ^ 16 * Range("m16").Value) + (x ^ 15 * Range("m15").Value) + (x ^ 14 * Range("m14").Value) + (x ^ 13 * Range("m13").Value) + (x ^ 12 * Range("m12").Value) + (x ^ 11 * Range("m11").Value) + (x ^ 10 * Range("m10").Value) + (x ^ 9 * Range("m9").Value) + (x ^ 8 * Range("m8").Value) + (x ^ 7 * Range("m7").Value) + (x ^ 6 * Range("m6").Value) + (x ^ 5 * Range("m5").Value) + (x ^ 4 * Range("m4").Value) + (x ^ 3 * Range("m3").Value) + (x ^ 2 * Range("m2").Value) + (x * Range("m1").Value) + Range("m21").Value
End Function
Public Sub Gra()
Sheets("Лист1").Select
Range("e1").Select
For i = -10 To 10
ActiveCell.Value = F(i)
ActiveCell.Cells(2).Select
Next i
End Sub
Public Function DetectBorders()
' Функция определения границ действительных корней
ma = 0
For Each curcell In Range("Koeffs")
If curcell.Value > ma Then ma = curcell.Value
If curcell.Value <> 0 Then Ao = curcell.Value
Next curcell
DetectBorders = 1 + (ma * Ao)
End Function
UNIT2
Sub auto_open()
Sheets("Лист1").Select
Form_Main.Show
End Sub
FORM_ABOUT
Private Sub CommandButton1_Click()
Form_About.Hide
End Sub
FORM_KOEFF
Private Sub CommandButton1_Click()
ko = TextBox1.Value
st = TextBox2.Value
Select Case st
Case 0
Range("A21").Value = ko
Case 1
Range("A1") = ko
Case 2
Range("A2") = ko
Case 3
Range("A3") = ko
Case 4
Range("A4") = ko
Case 5
Range("A5") = ko
Case 6
Range("A6") = ko
Case 7
Range("A7") = ko
Case 8
Range("A8") = ko
Case 9
Range("A9") = ko
Case 10
Range("A10") = ko
Case 11
Range("A11") = ko
Case 12
Range("A12") = ko
Case 13
Range("A13") = ko
Case 14
Range("A14") = ko
Case 15
Range("A15") = ko
Case 16
Range("A16") = ko
Case 17
Range("A17") = ko
Case 18
Range("A18") = ko
Case 19
Range("A19") = ko
Case 20
Range("A20") = ko
Case Else
MsgBox ("Выход за пределы допустимых значений")
st = st - 1
End Select
TextBox1.Value = 0
TextBox2.Value = st + 1
End Sub
Private Sub CommandButton2_Click()
Form_Koeff.Hide
End Sub
Private Sub CommandButton3_Click()
Range("a1").Value = 0
Range("a2").Value = 0
Range("a3").Value = 0
Range("a4").Value = 0
Range("a5").Value = 0
Range("a6").Value = 0
Range("a7").Value = 0
Range("a8").Value = 0
Range("a9").Value = 0
Range("a10").Value = 0
Range("a11").Value = 0
Range("a12").Value = 0
Range("a13").Value = 0
Range("a14").Value = 0
Range("a15").Value = 0
Range("a16").Value = 0
Range("a17").Value = 0
Range("a18").Value = 0
Range("a19").Value = 0
Range("a20").Value = 0
Range("a21").Value = 0
End Sub
Private Sub UserForm_initialize()
st = 0
ko = 0
TextBox1.Value = ko
TextBox2.Value = st
End Sub
FORM_KORNI
Private Sub CommandButton1_Click()
ListBox1.Clear
TextBox1.Value = 0
Form_Korni.Hide
End Sub
Private Sub CommandButton2_Click()
Range("Toc").Value = TextBox1.Value
Call FindKor
'Call Perenos
End Sub
Sub FindKor()
Range("Curright") = Range("Right").Value
Range("Curleft") = -Range("Right").Value - 0.333
'Range("right").Value = DetectBorders
Range("Stepleft").Value = Range("right").Value * (-1) - 0.333
Do
nashli = False
Call MoveLe
If Sgn(F(Range("curleft").Value)) = Sgn(F(Range("curright").Value)) Then
End If
If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curright").Value)) Then
Do
' nashli = True
Range("Curcenter").Value = ((Range("curleft").Value) + (Range("curright").Value)) / 2
If Abs(F(Range("Curcenter").Value)) > Range("toc").Value Then If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curcenter").Value)) Then Range("curright").Value = Range("curcenter").Value Else: Range("curleft").Value = Range("curcenter").Value
If Abs(F(Range("Curcenter").Value)) <= Range("toc").Value Then ListBox1.AddItem (Range("Curcenter").Value)
Range("Koren").Value = Range("Curcenter").Value
Loop Until Abs(F(Range("Curcenter").Value)) <= Range("toc").Value
End If
Loop Until Range("Stepleft").Value > Range("right").Value Or nashli = True
End Sub
Sub Horda_Kas()
'Sub FindKor()
Range("Curright") = Range("Right").Value
Range("Curleft") = -Range("Right").Value - 0.333
'Range("right").Value = DetectBorders
Range("Stepleft").Value = Range("right").Value * (-1) - 0.333
Do
MoveLe
If Sgn(F(Range("curleft").Value)) <> Sgn(F(Range("curright").Value)) Then
Do
' nashli = True
If F1(Range("curleft").Value) * F2(Range("curleft").Value) > 0 Then
Range("curleft").Value = Range("curleft").Value - ((Range("curright").Value - Range("curleft").Value) * (F(Range("Curleft").Value) / (F(Range("Curright").Value - F(Range("Curleft").Value)))))
Range("Curright").Value = Range("curright").Value - F(Range("curright").Value) / F1(Range("curright").Value)
End If
If F1(Range("curleft").Value) * F2(Range("curleft").Value) < 0 Then
Range("curright").Value = Range("curleft").Value - ((Range("curright").Value - Range("curleft").Value) * (F(Range("Curleft").Value) / (F(Range("Curright").Value - F(Range("Curleft").Value)))))
Range("Curleft").Value = Range("curright").Value - F(Range("curright").Value) / F1(Range("curright").Value)
End If
If Abs(Abs(F(Range("Curright").Value))) - Abs(F(Range("Curleft").Value)) <= Range("toc").Value Then
'MsgBox (Range("curleft").Value)
ListBox1.AddItem (Range("Curright").Value)
'If ((Range("Curleft").Value) + (Range("Curright").Value)) > 0 Then ListBox1.AddItem (((Range("Curleft").Value) + (Range("Curright").Value)) / 2)
'If ((Range("Curleft").Value) + (Range("Curright").Value)) < 0 Then ListBox1.AddItem (((Range("Curleft").Value) + (Range("Curright").Value)) / 2)
Range("Koren").Value = Range("Curleft").Value
End If
Loop Until Abs(F(Range("Curright").Value)) - Abs(F(Range("Curleft").Value)) <= Range("toc").Value
End If
Loop Until Range("Stepleft").Value > Range("right").Value Or nashli = True
End Sub
Sub MoveLe()
Range("stepleft").Value = Range("stepleft").Value + 0.333
Range("curLeft").Value = Range("stepleft").Value
Range("Curright").Value = Range("Curleft").Value + 0.333
Range("Curcenter").Value = ((Range("curleft").Value) + (Range("curright").Value)) / 2
End Sub
Private Sub CommandButton3_Click()
Horda_Kas
End Sub
Private Sub UserForm_Deactivate()
ListBox1.Clear
TextBox1.Value = 0
End Sub
Sub Perenos()
Range("a1").Value = Range("L1").Value
Range("a2").Value = Range("L2").Value
Range("a3").Value = Range("L3").Value
Range("a4").Value = Range("L4").Value
Range("a5").Value = Range("L5").Value
Range("a6").Value = Range("L6").Value
Range("a7").Value = Range("L7").Value
Range("a8").Value = Range("L8").Value
Range("a9").Value = Range("L9").Value
Range("a10").Value = Range("L10").Value
Range("a11").Value = Range("L11").Value
Range("a12").Value = Range("L12").Value
Range("a13").Value = Range("L13").Value
Range("a14").Value = Range("L14").Value
Range("a15").Value = Range("L15").Value
Range("a16").Value = Range("L16").Value
Range("a17").Value = Range("L17").Value
Range("a18").Value = Range("L18").Value
Range("a19").Value = Range("L19").Value
End Sub
FORM_MAIN
Private Sub CommandButton1_Click()
Form_Koeff.Show
End Sub
Private Sub CommandButton2_Click()
Form_Mnogo.Show
End Sub
Private Sub CommandButton3_Click()
Gra
Form_Main.Height = 84
Sheets("D1").Select
Form_WP.Show
Form_Main.Height = 360
Sheets("Лист1").Select
End Sub
Private Sub CommandButton4_Click()
Form_Korni.Show
End Sub
Private Sub CommandButton5_Click()
Application.Quit
End Sub
Private Sub CommandButton7_Click()
Form_About.Show
End Sub
Private Sub CommandButton8_Click()
ActiveWorkbook.Save
End Sub
Private Sub UserForm_initialize()
Sheets("Лист1").Select
Form_Main.Height = 360
End Sub
FORM_MNOGO
Dim mn As String
Private Sub CommandButton1_Click()
Form_Mnogo.Hide
End Sub
Private Sub UserForm_activate()
mn = "F(x)="
If Range("a20") > 0 Then mn = mn + Range("a20").Text + "X^20"
If Range("a20") < 0 Then mn = mn + Range("a20").Text + "X^20"
If Range("a19") > 0 Then mn = mn + " + " + Range("a19").Text + "X^19"
If Range("a19") < 0 Then mn = mn + Range("a19").Text + "X^19"
If Range("a18") > 0 Then mn = mn + " + " + Range("a18").Text + "X^18"
If Range("a18") < 0 Then mn = mn + Range("a18").Text + "X^18"
If Range("a17") > 0 Then mn = mn + " + " + Range("a17").Text + "X^17"
If Range("a17") < 0 Then mn = mn + Range("a17").Text + "X^17"
If Range("a16") > 0 Then mn = mn + " + " + Range("a16").Text + "X^16"
If Range("a16") < 0 Then mn = mn + Range("a16").Text + "X^16"
If Range("a15") > 0 Then mn = mn + " + " + Range("a15").Text + "X^15"
If Range("a15") < 0 Then mn = mn + Range("a15").Text + "X^15"
If Range("a14") > 0 Then mn = mn + " + " + Range("a14").Text + "X^14"
If Range("a14") < 0 Then mn = mn + Range("a14").Text + "X^14"
If Range("a13") > 0 Then mn = mn + " + " + Range("a13").Text + "X^13"
If Range("a13") < 0 Then mn = mn + Range("a13").Text + "X^13"
If Range("a12") > 0 Then mn = mn + " + " + Range("a12").Text + "X^12"
If Range("a12") < 0 Then mn = mn + Range("a12").Text + "X^12"
If Range("a11") > 0 Then mn = mn + " + " + Range("a11").Text + "X^11"
If Range("a11") < 0 Then mn = mn + Range("a11").Text + "X^11"
If Range("a10") > 0 Then mn = mn + " + " + Range("a10").Text + "X^10"
If Range("a10") < 0 Then mn = mn + Range("a10").Text + "X^10"
If Range("a9") > 0 Then mn = mn + " + " + Range("a9").Text + "X^9"
If Range("a9") < 0 Then mn = mn + Range("a9").Text + "X^9"
If Range("a8") > 0 Then mn = mn + " + " + Range("a8").Text + "X^8"
If Range("a8") < 0 Then mn = mn + Range("a8").Text + "X^8"
If Range("a7") > 0 Then mn = mn + " + " + Range("a7").Text + "X^7"
If Range("a7") < 0 Then mn = mn + Range("a7").Text + "X^7"
If Range("a6") > 0 Then mn = mn + " + " + Range("a6").Text + "X^6"
If Range("a6") < 0 Then mn = mn + Range("a6").Text + "X^6"
If Range("a5") > 0 Then mn = mn + " + " + Range("a5").Text + "X^5"
If Range("a5") < 0 Then mn = mn + Range("a5").Text + "X^5"
If Range("a4") > 0 Then mn = mn + " + " + Range("a4").Text + "X^4"
If Range("a4") < 0 Then mn = mn + Range("a4").Text + "X^4"
If Range("a3") > 0 Then mn = mn + " + " + Range("a3").Text + "X^3"
If Range("a3") < 0 Then mn = mn + Range("a3").Text + "X^3"
If Range("a2") > 0 Then mn = mn + " + " + Range("a2").Text + "X^2"
If Range("a2") < 0 Then mn = mn + Range("a2").Text + "X^2"
If Range("a1") > 0 Then mn = mn + " + " + Range("a1").Text + "X"
If Range("a1") < 0 Then mn = mn + Range("a8").Text + "X"
If Range("a21") > 0 Then mn = mn + " + " + Range("a21").Text
If Range("a21") < 0 Then mn = mn + Range("a21").Text
TextBox1.Value = mn
End Sub
FORM_WP
Private Sub Label1_Click()
Call Gra
End Sub
Private Sub CommandButton1_Click()
Sheets("D1").Print
End Sub
Private Sub CommandButton2_Click()
Form_WP.Hide
Call Gra
End Sub
Private Sub UserForm_Click()
Form_WP.Hide
End Sub
____________________________
VoID InVaSiON HG ©
VI Function 2.0 beta
[1] Этот факт был доказан известными математиками Абелеи и Галуа.
