Создание программы для решения нелинейных уравнений
Міністерство
освіти та науки України
Житомирський
державний технологічний університет
Звіт до розрахункової роботи
з предмету «Емпіричні
методи програмної інженерії»
Виконав: К. Д. Саєцький
Перевірив: В. О. Скачков
Житомир 2011
р.
Содержание
1. Задание
. Разработка
программы
.1
Теоретические сведения для решения задачи
.
Тестирование программы
. Дополнения
.1
Руководство пользователя
.2 Листинг
программы
Выводы
1. Задание
Реализовать доступными методами программу для ПК, которая находит решение
нелинейного уравнения следующими способами:
Методом Ньютона
Методом Хорд
Модифицированным методом Ньютона
Методом простых итераций
Также программа должна иметь возможность ввода пользователем:
- коэффициентов
длину
отрезка , его шаг
для задания точности вычислений
В качестве нашего нелинейного уравнения возьмём уравнение:
Производная
от данного уравнения:
2.
Разработка программы
.1Теоретические
сведения для решения
нелинейный
уравнение компьютер программа
Нелинейное уравнение - уравнение,
в котором неизвестные величины (числа, функции, векторы и т. д.) входят не
только линейным образом.
Метод Ньютона
Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) -
это итерационный численный метод нахождения корня (нуля) заданной функции.
Поиск решения осуществляется путём построения последовательных приближений и
основан на принципах простой итерации. Метод обладает квадратичной сходимостью.
Улучшением метода является метод хорд и касательных.
Геометрическая интерпретация
Основная идея метода заключается в следующем: задаётся начальное
приближение вблизи предположительного корня, после чего строится касательная к
исследуемой функции в точке приближения, для которой находится пересечение с
осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так
далее, пока не будет достигнута необходимая точность.
Алгоритм
1. Задается начальное приближение x0.
. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных
пределах), вычисляют новое приближение:
Условия применения
Рассмотрим ряд примеров, указывающих на недостатки метода.
Если начальное приближение недостаточно близко к решению, то метод может
не сойтись.
Если производная не непрерывна в точке корня, то метод может расходиться
в любой окрестности корня.
Если не существует вторая производная в точке корня, то скорость
сходимости метода может быть заметно снижена.
Если производная в точке корня равна нулю, то скорость сходимости не
будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать
неверное для заданной точности приближение.
Метод одной касательной
В целях уменьшения числа обращений к значениям производной функции
применяют так называемый метод одной касательной.
Формула итераций этого метода имеет вид:
Суть метода заключается в том, чтобы вычислять производную лишь один раз,
в точке начального приближения , а затем использовать это значение на каждой
последующей итерации.
Метод хорд
Метод хорд - итерационный численный метод приближённого нахождения корня
алгебраического уравнения.
Геометрическое описание
Будем искать корень функции f(x). Выберем две начальные точки C1(x1;y1)
и C2(x2;y2) и проведем через них прямую. Она
пересечет ось абсцисс в точке (x3;0). Теперь найдем значение функции
с абсциссой x3. Временно будем считать x3 корнем на
отрезке [x1;x2]. Пусть точка C3 имеет абсциссу
x3 и лежит на графике. Теперь вместо точек C1 и C2
мы возьмём точку C3 и точку C2. Теперь с этими двумя
точками проделаем ту же операцию и так далее, то есть будем получать две точки
Cn + 1 и Cn и повторять операцию с ними. Отрезок,
соединяющий последние 2 точки, пересекает ось абсцисс в точке, значение
абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять
до тех пор, пока не получим значение корня с нужным приближением.
Критерий сходимости
Если
дважды непрерывно дифференцируемая функция и знак сохраняется на рассматриваемом промежутке, то
полученные приближения будут сходиться к корню монотонно. Если корень уравнения находится
на отрезке , производные и на этом промежутке непрерывны и сохраняют постоянные
знаки и , то можно доказать, что погрешность приближенного
решения стремится к нулю при n→∞, то есть метод сходится и сходится
со скоростью геометрической прогрессии (при этом говорят, что он имеет линейную
скорость сходимости.
Метод
простой итерации
В
основе метода заложено понятие сжимающего отображения. Говорят, что функция осуществляет сжимающее отображение на , если
.
.
Если
- сжимающее отображение на , то:
. - корень;
. итерационная
последовательность сходится к этому корню;
. для
очередного члена справедливо
Поясним
смысл параметра . Согласно теореме Лагранжа имеем:
Отсюда
следует, что . Таким образом, для сходимости метода достаточно,
чтобы
.
Алгоритм
1. Условие
преобразуется к виду , где -сжимающая
. Задаётся
начальное приближение и точность
. Вычисляется
очередная итерация
o Если
, то и
возврат к шагу 3.
o Иначе
и остановка.
3. Тестирование программы
Для проверки работы программы было введено несколько контрольных
примеров. Результаты программы проверялись с реальными значениями.
Пример 1:
Введены следующие данные:
Табулируем
функцию:
0:
1
,1:1,4420
,2:1,9760
,3:2,6140
,4:3,3680
,5:4,25
,6:5,2720
,7:6,4459
,8:7,7840
,9:9,2980
Результат
работы метода Ньютона:
Находим
x0: 5,149
Находим
x1: 3,187494
Находим
x2: 1,870224
Находим
x3: 0,9801983
Находим
x4: 0,3754452
Находим
x5: -0,02859786
Находим
x6: -0,2639803
Находим
x7: -0,3446429
Находим
x8: -0,3521451
Находим
x9: -0,3522011
Результат
работы метода Хорд:
Находим
x0: 9,298
Находим
x1: 1
Находим
x2: 0,9539158
Находим
x3: 0,3729838
Находим
x4: 0,1128457
Находим
x5: -0,1248965
Находим
x6: -0,2653174
Находим
x7: -0,3336487
Находим
x8: -0,3506245
Находим
x9: -0,3521724
Результат
работы метода Итераций:
Находим
x0: 5,149
Находим
x1: 0
Находим
x2: -2,5745
Находим
x3: -1,28725
Находим
x4: -0,643625
Находим
x5: -0,321812
Находим
x6: -0,482718
Находим
x7: -0,402265
Находим
x8: -0,362039
Находим
x9: -0,341925
Находим
x10: -0,351982
Находим
x11: -0,357010
Находим
x12: -0,354496
Находим
x13: -0,353239
Находим
x14: -0,352611
Находим
x15: -0,352296
Находим
x16: -0,352139
Находим
x17: -0,352218
Результат
работы модифицированного метода Ньютона:
Находим
x0: 5,149
Находим
x1: 3,187494
Находим
x2: 2,60413
Находим
x3: 2,24253
Находим
x4: 1,984821
Находим
x5: 1,787353
Находим
x7: 1,497908
Находим
x8: 1,386835
Находим
x9: 1,291002
Находим
x10: 1,20712
Находим
x11: 1,13283
Находим
x12: 1,066387
Находим
x13: 1,006467
Находим
x14: 0,9520432
Находим
x412: -0,3415772
Находим
x413: -0,3416785
Находим
x414: -0,3417788
Находим
x415: -0,3418781
Пример
2:
Введены
следующие данные:
Табулируем
функцию:
0:
12
,1:12,281
,2:12,528
,3:12,747
,4:12,944
,5:13,125
,6:13,296
,7:13,462
,8:13,632
,9:13,809
Результат
работы метода Ньютона:
Находим
x0: 12,9045
Находим
x1: 8,765339
Находим
x2: 5,952867
Находим
x3: 3,965287
Находим
x4: 2,368141
Находим
x5: 0,3231664
Находим
x6: -6,008665
Находим
x7: -3,827814
Находим
x8: -2,464772
Находим
x9: -1,740349
Находим
x10: -1,501484
Находим
x11: -1,47622
Находим
x12: -1,475953
Результат
работы метода Хорд:
Находим
x0: 13,809
Находим
x1: 12
Находим
x2: 8,70635
Находим
x3: 6,794728
Находим
x4: 5,137582
Находим
x5: 3,864838
Находим
x6: 2,750797
Находим
x7: 1,618523
Находим
x8: -0,1630604
Находим
x9: -4,797469
Находим
x10: -0,4747522
Находим
x11: -0,7312077
Находим
x12: -2,011457
Находим
x13: -1,305346
Находим
x14: -1,441493
Находим
x15: -1,478537
Находим
x16: -1,475915
Результат
работы метода Итераций:
Находим
x0: 12,9045
Находим
x1: 0
Находим
x2: -6,45225
Находим
x3: -3,226125
Находим
x4: -1,613063
Находим
x5: -0,806531
Находим
x6: -1,209797
Находим
x7: -1,41143
Находим
x8: -1,512246
Находим
x9: -1,461838
Находим
x11: -1,47444
Находим
x12: -1,480741
Находим
x13: -1,47759
Находим
x14: -1,476015
Находим
x15: -1,475227
Результат
работы модифицированного метода Ньютона:
Находим
x0: 12,9045
Находим
x1: 8,765339
Находим
x2: 7,527792
Находим
x3: 6,756481
Находим
x4: 6,203433
Находим
x5: 5,776856
Находим
x6: 5,43232
Находим
x7: 5,144967
Находим
x8: 4,899525
Находим
x9: 4,685975
Находим
x10: 4,497405
Находим
x240: -1,444884
Находим
x241: -1,445934
Находим
x242: -1,446949
Находим
x243: -1,44793
4.
Дополнения
.1
Руководство пользователя
Руководство
пользователя основано на примере тестирования программы, пункт 3(см. стр. 6).
Для
запуска данного программного продукта необходим установленный пакет .NET
Framework не ниже версии 2.0.
1) Откройте запускной файл программы “NL.exe”. Откроется окно с
программой. (Рис 1.1)
Рис. 1.1
) Введите данные в поля “a0, a1, a2, a3”, “Xo”, “Xn”, “h”, “ε”
и нажмите на одну из
кнопок внизу окна приложения, в зависимости какой метод Вы желаете
использовать. После нажатия на кнопку(на примере кнопка “Ньютон”) в полях
“Табулирование” и “Вывод” появятся результаты работы программы. (Рис 1.2)
Рис.
1.2
4.2 Листинг программы
float[] a = new float[4];fx(float x)
{ return a[0] * Math.Pow(x, 3) + a[1] * Math.Pow(x, 2) + a[2]
* x + a[3]; }fxS(float x)
{ return 3* a[0] * Math.Pow(x, 2) + 2 * a[1] * x + a[2];
}void button1_Click(object sender, EventArgs e)
{.Clear();.Clear();x0, xn, h;n = 0;[] x;[] t =
textBox5.Text.Split(" ,".ToCharArray(),
StringSplitOptions.RemoveEmptyEntries);(int i = 0; i < a.Length; i++)[i] =
Convert.ToSingle(t[i]);eps = Convert.ToSingle(textBox7.Text);=
Convert.ToSingle(textBox1.Text);= Convert.ToSingle(textBox2.Text);=
Convert.ToSingle(textBox6.Text);= Convert.ToInt32(xn / h);= new
float[n*n*n];first = 0, last = 0;k = 0;(double i = x0; i < xn; i+=h)
{++;val = fx((float)i);(k == 1) first = val;(k == n) last =
val;(Convert.ToString(i).Length == 1)
{.Text += i + ": \t" + val + Environment.NewLine;;
}(Convert.ToString(i).Length >
3)(Convert.ToString(val).Length > 6).Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" + Convert.ToString(val).Substring(0,
6) + Environment.NewLine;.Text += Convert.ToString(i).Substring(0, 3) +
":\t" + val + Environment.NewLine;.Text += i + ": " + val +
Environment.NewLine;
}[0] = Convert.ToSingle((last + first) / 2.0);.Text +=
"Находим x0: " + x[0] + Environment.NewLine;j = 0;(Math.Abs(fx(x[j]))
> eps)
{[j + 1] = x[j] - (float)(fx(x[j]) / fxS(x[j]));.Text +=
"Находим x" + (j + 1) + ": " + x[j + 1] +
Environment.NewLine;++;
}
}void button2_Click(object sender, EventArgs e)
{.Clear();.Clear();x0, xn, h;n = 0;[] x;[] t =
textBox5.Text.Split(" ,".ToCharArray(),
StringSplitOptions.RemoveEmptyEntries);(int i = 0; i < a.Length; i++)[i] =
Convert.ToSingle(t[i]);eps = Convert.ToSingle(textBox7.Text);=
Convert.ToSingle(textBox1.Text);= Convert.ToSingle(textBox2.Text);=
Convert.ToSingle(textBox6.Text);= Convert.ToInt32(xn / h);= new
float[n*n*n];first = 0, last = 0;k = 0;(double i = x0; i < xn; i += h)
{++;val = fx((float)i);(k == 1) first = val;(k == n) last =
val;(Convert.ToString(i).Length == 1)
{.Text += i + ": \t" + val + Environment.NewLine;;
}(Convert.ToString(i).Length >
3)(Convert.ToString(val).Length > 6).Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" +
Convert.ToString(val).Substring(0, 6) + Environment.NewLine;.Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" + val +
Environment.NewLine;.Text += i + ": " + val + Environment.NewLine;
}[0] = (float)last;[1] = (float)first;.Text += "Находим
x0: " + x[0] + Environment.NewLine;.Text += "Находим x1: " +
x[1] + Environment.NewLine;j = 1;(Math.Abs(fx(x[j])) > eps)
{[j + 1] = x[j] - (float)(fx(x[j]) * (x[j] - x[j - 1])) /
(float)(fx(x[j]) - fx(x[j - 1]));.Text += "Находим x" + (j + 1) +
": " + x[j + 1] + Environment.NewLine;++;
}
}void button3_Click(object sender, EventArgs e)
{.Clear();.Clear();x0, xn, h;n = 0;[] x;[] t =
textBox5.Text.Split(" ,".ToCharArray(),
StringSplitOptions.RemoveEmptyEntries);(int i = 0; i < a.Length; i++)[i] =
Convert.ToSingle(t[i]);eps = Convert.ToSingle(textBox7.Text);=
Convert.ToSingle(textBox1.Text);= Convert.ToSingle(textBox2.Text);=
Convert.ToSingle(textBox6.Text);= Convert.ToInt32(xn / h);= new float[n*n*n];
//табулированиеfirst = 0, last = 0;k = 0;(double i = x0; i
< xn; i += h)
{++;val = fx((float)i);(k == 1) first = val;(k == n) last =
val;(Convert.ToString(i).Length == 1)
{.Text += i + ": \t" + val + Environment.NewLine;;
}(Convert.ToString(i).Length >
3)(Convert.ToString(val).Length > 6).Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" +
Convert.ToString(val).Substring(0, 6) + Environment.NewLine;.Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" + val +
Environment.NewLine;.Text += i + ": " + val + Environment.NewLine;
}[0] = (float)(first + last) / 2.0f;[1] = -x[0];.Text +=
"Находим x0: " + x[0] + Environment.NewLine;j = 0;x1 = 0, x2 = 0, x22
= 0;= x[0];= x[1];(Math.Abs(x2 - x22) > eps || j < 2)
{= x2;= (x1 + x0) / 2;(fx(x2) > 0)
{= (x1 + x0) / 2; ;
}
{= (x1 + x0) / 2; ;
}(Convert.ToString(x2).Length >= 9).Text += "Находим
x" + (j + 1) + ": " + Convert.ToString(x2).Substring(0, 9) +
Environment.NewLine;.Text += "Находим x" + (j + 1) + ": " +
x2 + Environment.NewLine;++;(j > 150);
}
}void button4_Click(object sender, EventArgs e)
{.Clear();.Clear();x0, xn, h;n = 0;[] x;[] t =
textBox5.Text.Split(" ,".ToCharArray(),
StringSplitOptions.RemoveEmptyEntries);(int i = 0; i < a.Length; i++)[i] =
Convert.ToSingle(t[i]);eps = Convert.ToSingle(textBox7.Text);=
Convert.ToSingle(textBox1.Text);= Convert.ToSingle(textBox2.Text);=
Convert.ToSingle(textBox6.Text);= Convert.ToInt32(xn / h);= new
float[n*n*n*n];first = 0, last = 0;k = 0;(double i = x0; i < xn; i += h)
{++;val = fx((float)i);(k == 1) first = val;(k == n) last =
val;(Convert.ToString(i).Length == 1)
{.Text += i + ": \t" + val + Environment.NewLine;;
}(Convert.ToString(i).Length > 3)(Convert.ToString(val).Length
> 6).Text += Convert.ToString(i).Substring(0, 3) + ":\t" +
Convert.ToString(val).Substring(0, 6) + Environment.NewLine;.Text +=
Convert.ToString(i).Substring(0, 3) + ":\t" + val +
Environment.NewLine;.Text += i + ": " + val + Environment.NewLine;
}[0] = /* 0.5f;*/ Convert.ToSingle((last + first) /
2.0);.Text += "Находим x0: " + x[0] + Environment.NewLine;proizv =
fxS(x[0]);x1 = 0;i1 = 0;(Math.Abs(x1 - x[i1]) > eps)
{= x[i1];[i1 + 1] = x[i1] - (float)(fx(x[i1]) / proizv);.Text
+= "Находим x" + (i1 + 1) + ": " + x[i1 + 1] +
Environment.NewLine;++;(i1 > n*n*n);
}
Вывод
В
данной работе были изучены методы решения нелинейных уравнений, такие как:
метод Ньютона, модифицированный метод Ньютона, метод Хорд, метод простых
Итераций. Была создана программа для автоматизации данного процесса на примере
уравнения с учетом указанных погрешностей и возможностью ввода
данных пользователем. Получены навыки работы с нелинейными уравнениями.