Создание программы для решения нелинейных уравнений

Міністерство освіти та науки України Житомирський державний технологічний університет Звіт до розрахункової роботи з предмету «Емпіричні методи програмної інженерії»

Виконав: К. Д. Саєцький Перевірив: В. О. Скачков Житомир 2011 р.

1. Задание

2. Разработка программы

2.1 Теоретические сведения для решения задачи

3. Тестирование программы

4. Дополнения

4.1 Руководство пользователя

4.2 Листинг программы Выводы

1. Задание

Реализовать доступными методами программу для ПК, которая находит решение нелинейного уравнения следующими способами:

— Методом Ньютона

— Методом Хорд

— Модифицированным методом Ньютона

— Методом простых итераций Также программа должна иметь возможность ввода пользователем:

— коэффициентов

— длину отрезка, его шаг

— для задания точности вычислений В качестве нашего нелинейного уравнения возьмём уравнение:

Производная от данного уравнения:

2. Разработка программы

2.1Теоретические сведения для решения

нелинейный уравнение компьютер программа Нелинейное уравнение — уравнение, в котором неизвестные величины (числа, функции, векторы и т. д.) входят не только линейным образом.

Метод Ньютона

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных.

Геометрическая интерпретация

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Алгоритм

1. Задается начальное приближение x0.

2. Пока не выполнено условие остановки, в качестве которого можно взять или (то есть погрешность в нужных пределах), вычисляют новое приближение:

Условия применения

Рассмотрим ряд примеров, указывающих на недостатки метода.

— Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

— Если производная не непрерывна в точке корня, то метод может расходиться в любой окрестности корня.

— Если не существует вторая производная в точке корня, то скорость сходимости метода может быть заметно снижена.

— Если производная в точке корня равна нулю, то скорость сходимости не будет квадратичной, а сам метод может преждевременно прекратить поиск, и дать неверное для заданной точности приближение.

Метод одной касательной

В целях уменьшения числа обращений к значениям производной функции применяют так называемый метод одной касательной.

Формула итераций этого метода имеет вид:

Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения, а затем использовать это значение на каждой последующей итерации.

Метод хорд

Метод хорд — итерационный численный метод приближённого нахождения корня алгебраического уравнения.

Геометрическое описание

Будем искать корень функции f (x). Выберем две начальные точки C₁(x₁;y₁) и C₂(x₂;y₂) и проведем через них прямую. Она пересечет ось абсцисс в точке (x₃;0). Теперь найдем значение функции с абсциссой x₃. Временно будем считать x₃ корнем на отрезке [x₁;x₂]. Пусть точка C₃ имеет абсциссу x₃ и лежит на графике. Теперь вместо точек C₁ и C₂ мы возьмём точку C₃ и точку C₂. Теперь с этими двумя точками проделаем ту же операцию и так далее, то есть будем получать две точки C_{n + 1} и C_n и повторять операцию с ними. Отрезок, соединяющий последние 2 точки, пересекает ось абсцисс в точке, значение абсциссы которой можно приближённо считать корнем. Эти действия нужно повторять до тех пор, пока не получим значение корня с нужным приближением.

Критерий сходимости

Если дважды непрерывно дифференцируемая функция и знак сохраняется на рассматриваемом промежутке, то полученные приближения будут сходиться к корню монотонно. Если корень уравнения находится на отрезке, производные и на этом промежутке непрерывны и сохраняют постоянные знаки и, то можно доказать, что погрешность приближенного решения стремится к нулю при n>?, то есть метод сходится и сходится со скоростью геометрической прогрессии (при этом говорят, что он имеет линейную скорость сходимости.

Метод простой итерации

В основе метода заложено понятие сжимающего отображения. Говорят, что функция осуществляет сжимающее отображение на, если

1.

2.

Если — сжимающее отображение на, то:

1. — корень;

2. итерационная последовательность сходится к этому корню;

3. для очередного члена справедливо

Поясним смысл параметра. Согласно теореме Лагранжа имеем:

Отсюда следует, что. Таким образом, для сходимости метода достаточно, чтобы

1.

и так далее, пока

Алгоритм

1. Условие преобразуется к виду, гдесжимающая

2. Задаётся начальное приближение и точность

3. Вычисляется очередная итерация

o Если, то и возврат к шагу 3.

o Иначе и остановка.

3. Тестирование программы

Для проверки работы программы было введено несколько контрольных примеров. Результаты программы проверялись с реальными значениями.

Пример 1:

Введены следующие данные:

Табулируем функцию:

0: 1

0,1:1,4420

0,2:1,9760

0,3:2,6140

0,4:3,3680

0,5:4,25

0,6:5,2720

0,7:6,4459

0,8:7,7840

0,9:9,2980

Результат работы метода Ньютона:

Находим x0: 5,149

Находим x1: 3,187 494

Находим x2: 1,870 224

Находим x3: 0,9 801 983

Находим x4: 0,3 754 452

Находим x5: -0,2 859 786

Находим x6: -0,2 639 803

Находим x7: -0,3 446 429

Находим x8: -0,3 521 451

Находим x9: -0,3 522 011

Результат работы метода Хорд:

Находим x0: 9,298

Находим x1: 1

Находим x2: 0,9 539 158

Находим x3: 0,3 729 838

Находим x4: 0,1 128 457

Находим x5: -0,1 248 965

Находим x6: -0,2 653 174

Находим x7: -0,3 336 487

Находим x8: -0,3 506 245

Находим x9: -0,3 521 724

Результат работы метода Итераций:

Находим x0: 5,149

Находим x1: 0

Находим x2: -2,5745

Находим x3: -1,28 725

Находим x4: -0,643 625

Находим x5: -0,321 812

Находим x6: -0,482 718

Находим x7: -0,402 265

Находим x8: -0,362 039

Находим x9: -0,341 925

Находим x10: -0,351 982

Находим x11: -0,357 010

Находим x12: -0,354 496

Находим x13: -0,353 239

Находим x14: -0,352 611

Находим x15: -0,352 296

Находим x16: -0,352 139

Находим x17: -0,352 218

Результат работы модифицированного метода Ньютона:

Находим x0: 5,149

Находим x1: 3,187 494

Находим x2: 2,60 413

Находим x3: 2,24 253

Находим x4: 1,984 821

Находим x5: 1,787 353

Находим x6: 1,628 991

Находим x7: 1,497 908

Находим x8: 1,386 835

Находим x9: 1,291 002

Находим x10: 1,20 712

Находим x11: 1,13 283

Находим x12: 1,66 387

Находим x13: 1,6 467

Находим x14: 0,9 520 432

Находим x412: -0,3 415 772

Находим x413: -0,3 416 785

Находим x414: -0,3 417 788

Находим x415: -0,3 418 781

Пример 2:

Введены следующие данные:

Табулируем функцию:

0: 12

0,1:12,281

0,2:12,528

0,3:12,747

0,4:12,944

0,5:13,125

0,6:13,296

0,7:13,462

0,8:13,632

0,9:13,809

Результат работы метода Ньютона:

Находим x0: 12,9045

Находим x1: 8,765 339

Находим x2: 5,952 867

Находим x3: 3,965 287

Находим x4: 2,368 141

Находим x5: 0,3 231 664

Находим x6: -6,8 665

Находим x7: -3,827 814

Находим x8: -2,464 772

Находим x9: -1,740 349

Находим x10: -1,501 484

Находим x11: -1,47 622

Находим x12: -1,475 953

Результат работы метода Хорд:

Находим x0: 13,809

Находим x1: 12

Находим x2: 8,70 635

Находим x3: 6,794 728

Находим x4: 5,137 582

Находим x5: 3,864 838

Находим x6: 2,750 797

Находим x7: 1,618 523

Находим x8: -0,1 630 604

Находим x9: -4,797 469

Находим x10: -0,4 747 522

Находим x11: -0,7 312 077

Находим x12: -2,11 457

Находим x13: -1,305 346

Находим x14: -1,441 493

Находим x15: -1,478 537

Находим x16: -1,475 915

Результат работы метода Итераций:

Находим x0: 12,9045

Находим x1: 0

Находим x2: -6,45 225

Находим x3: -3,226 125

Находим x4: -1,613 063

Находим x5: -0,806 531

Находим x6: -1,209 797

Находим x7: -1,41 143

Находим x8: -1,512 246

Находим x9: -1,461 838

Находим x10: -1,487 042

Находим x11: -1,47 444

Находим x12: -1,480 741

Находим x13: -1,47 759

Находим x14: -1,476 015

Находим x15: -1,475 227

Результат работы модифицированного метода Ньютона:

Находим x0: 12,9045

Находим x1: 8,765 339

Находим x2: 7,527 792

Находим x3: 6,756 481

Находим x4: 6,203 433

Находим x5: 5,776 856

Находим x6: 5,43 232

Находим x7: 5,144 967

Находим x8: 4,899 525

Находим x9: 4,685 975

Находим x10: 4,497 405

Находим x240: -1,444 884

Находим x241: -1,445 934

Находим x242: -1,446 949

Находим x243: -1,44 793

4. Дополнения

4.1 Руководство пользователя

Руководство пользователя основано на примере тестирования программы, пункт 3(см. стр. 6).

Для запуска данного программного продукта необходим установленный пакет .NET Framework не ниже версии 2.0.

1) Откройте запускной файл программы «NL.exe». Откроется окно с программой. (Рис 1.1)

Рис. 1.1

2) Введите данные в поля «a0, a1, a2, a3», «Xo», «Xn», «h», «е» и нажмите на одну из кнопок внизу окна приложения, в зависимости какой метод Вы желаете использовать. После нажатия на кнопку (на примере кнопка «Ньютон») в полях «Табулирование» и «Вывод» появятся результаты работы программы. (Рис 1.2)

Рис. 1.2

4.2 Листинг программы

float[] a = new float[4];

double fx (float x)

{ return a[0] * Math. Pow (x, 3) + a[1] * Math. Pow (x, 2) + a[2] * x + a[3]; }

double fxS (float x)

{ return 3* a[0] * Math. Pow (x, 2) + 2 * a[1] * x + a[2]; }

private void button1_Click (object sender, EventArgs e)

{

textBox3.Clear ();

textBox4.Clear ();

float x0, xn, h;

int n = 0;

float[] x;

string[] t = textBox5.Text.Split («,» .ToCharArray (), StringSplitOptions. RemoveEmptyEntries);

for (int i = 0; i < a. Length; i++)

a[i] = Convert. ToSingle (t[i]);

float eps = Convert. ToSingle (textBox7.Text);

x0 = Convert. ToSingle (textBox1.Text);

xn = Convert. ToSingle (textBox2.Text);

h = Convert. ToSingle (textBox6.Text);

n = Convert. ToInt32(xn / h);

x = new float[n*n*n];

double first = 0, last = 0;

int k = 0;

for (double i = x0; i < xn; i+=h)

{

k++;

double val = fx ((float)i);

if (k == 1) first = val;

if (k == n) last = val;

if (Convert.ToString (i).Length == 1)

{

textBox3.Text += i + «: t» + val + Environment. NewLine;

continue;

}

if (Convert.ToString (i).Length > 3)

if (Convert.ToString (val).Length > 6)

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + Convert. ToString (val).Substring (0, 6) + Environment. NewLine;

else

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + val + Environment. NewLine;

else

textBox3.Text += i + «: «+ val + Environment. NewLine;

}

x[0] = Convert. ToSingle ((last + first) / 2.0);

textBox4.Text += «Находим x0: «+ x[0] + Environment. NewLine;

int j = 0;

while (Math.Abs (fx (x[j])) > eps)

{

x[j + 1] = x[j] - (float)(fx (x[j]) / fxS (x[j]));

textBox4.Text += «Находим x» + (j + 1) + «: «+ x[j + 1] + Environment. NewLine;

j++;

}

}

private void button2_Click (object sender, EventArgs e)

{

textBox3.Clear ();

textBox4.Clear ();

float x0, xn, h;

int n = 0;

float[] x;

string[] t = textBox5.Text.Split («,» .ToCharArray (), StringSplitOptions. RemoveEmptyEntries);

for (int i = 0; i < a. Length; i++)

a[i] = Convert. ToSingle (t[i]);

float eps = Convert. ToSingle (textBox7.Text);

x0 = Convert. ToSingle (textBox1.Text);

xn = Convert. ToSingle (textBox2.Text);

h = Convert. ToSingle (textBox6.Text);

n = Convert. ToInt32(xn / h);

x = new float[n*n*n];

double first = 0, last = 0;

int k = 0;

for (double i = x0; i < xn; i += h)

{

k++;

double val = fx ((float)i);

if (k == 1) first = val;

if (k == n) last = val;

if (Convert.ToString (i).Length == 1)

{

textBox3.Text += i + «: t» + val + Environment. NewLine;

continue;

}

if (Convert.ToString (i).Length > 3)

if (Convert.ToString (val).Length > 6)

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + Convert. ToString (val).Substring (0, 6) + Environment. NewLine;

else

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + val + Environment. NewLine;

else

textBox3.Text += i + «: «+ val + Environment. NewLine;

}

x[0] = (float)last;

x[1] = (float)first;

textBox4.Text += «Находим x0: «+ x[0] + Environment. NewLine;

textBox4.Text += «Находим x1: «+ x[1] + Environment. NewLine;

int j = 1;

while (Math.Abs (fx (x[j])) > eps)

{

x[j + 1] = x[j] - (float)(fx (x[j]) * (x[j] - x[j — 1])) / (float)(fx (x[j]) — fx (x[j — 1]));

textBox4.Text += «Находим x» + (j + 1) + «: «+ x[j + 1] + Environment. NewLine;

j++;

}

}

private void button3_Click (object sender, EventArgs e)

{

textBox3.Clear ();

textBox4.Clear ();

float x0, xn, h;

int n = 0;

float[] x;

string[] t = textBox5.Text.Split («,» .ToCharArray (), StringSplitOptions. RemoveEmptyEntries);

for (int i = 0; i < a. Length; i++)

a[i] = Convert. ToSingle (t[i]);

float eps = Convert. ToSingle (textBox7.Text);

x0 = Convert. ToSingle (textBox1.Text);

xn = Convert. ToSingle (textBox2.Text);

h = Convert. ToSingle (textBox6.Text);

n = Convert. ToInt32(xn / h);

x = new float[n*n*n];

//табулирование

double first = 0, last = 0;

int k = 0;

for (double i = x0; i < xn; i += h)

{

k++;

double val = fx ((float)i);

if (k == 1) first = val;

if (k == n) last = val;

if (Convert.ToString (i).Length == 1)

{

textBox3.Text += i + «: t» + val + Environment. NewLine;

continue;

}

if (Convert.ToString (i).Length > 3)

if (Convert.ToString (val).Length > 6)

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + Convert. ToString (val).Substring (0, 6) + Environment. NewLine;

else

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + val + Environment. NewLine;

else

textBox3.Text += i + «: «+ val + Environment. NewLine;

}

x[0] = (float)(first + last) / 2.0f;

x[1] = -x[0];

textBox4.Text += «Находим x0: «+ x[0] + Environment. NewLine;

int j = 0;

float x1 = 0, x2 = 0, x22 = 0;

x0 = x[0];

x1 = x[1];

while (Math.Abs (x2 — x22) > eps || j < 2)

{

x22 = x2;

x2 = (x1 + x0) / 2;

if (fx (x2) > 0)

{

x0 = (x1 + x0) / 2; ;

}

else

{

x1 = (x1 + x0) / 2; ;

}

if (Convert.ToString (x2).Length >= 9)

textBox4.Text += «Находим x» + (j + 1) + «: «+ Convert. ToString (x2).Substring (0, 9) + Environment. NewLine;

else

textBox4.Text += «Находим x» + (j + 1) + «: «+ x2 + Environment. NewLine;

j++;

if (j > 150)

break;

}

}

private void button4_Click (object sender, EventArgs e)

{

textBox3.Clear ();

textBox4.Clear ();

float x0, xn, h;

int n = 0;

float[] x;

string[] t = textBox5.Text.Split («,» .ToCharArray (), StringSplitOptions. RemoveEmptyEntries);

for (int i = 0; i < a. Length; i++)

a[i] = Convert. ToSingle (t[i]);

float eps = Convert. ToSingle (textBox7.Text);

x0 = Convert. ToSingle (textBox1.Text);

xn = Convert. ToSingle (textBox2.Text);

h = Convert. ToSingle (textBox6.Text);

n = Convert. ToInt32(xn / h);

x = new float[n*n*n*n];

double first = 0, last = 0;

int k = 0;

for (double i = x0; i < xn; i += h)

{

k++;

double val = fx ((float)i);

if (k == 1) first = val;

if (k == n) last = val;

if (Convert.ToString (i).Length == 1)

{

textBox3.Text += i + «: t» + val + Environment. NewLine;

continue;

}

if (Convert.ToString (i).Length > 3)

if (Convert.ToString (val).Length > 6)

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + Convert. ToString (val).Substring (0, 6) + Environment. NewLine;

else

textBox3.Text += Convert. ToString (i).Substring (0, 3) + «:t» + val + Environment. NewLine;

else

textBox3.Text += i + «: «+ val + Environment. NewLine;

}

x[0] = /* 0.5f;*/ Convert. ToSingle ((last + first) / 2.0);

textBox4.Text += «Находим x0: «+ x[0] + Environment. NewLine;

double proizv = fxS (x[0]);

float x1 = 0;

int i1 = 0;

while (Math.Abs (x1 — x[i1]) > eps)

{

x1 = x[i1];

x[i1 + 1] = x[i1] - (float)(fx (x[i1]) / proizv);

textBox4.Text += «Находим x» + (i1 + 1) + «: «+ x[i1 + 1] + Environment. NewLine;

i1++;

if (i1 > n*n*n)

break;

}

}

Вывод

В данной работе были изучены методы решения нелинейных уравнений, такие как: метод Ньютона, модифицированный метод Ньютона, метод Хорд, метод простых Итераций. Была создана программа для автоматизации данного процесса на примере уравнения с учетом указанных погрешностей и возможностью ввода данных пользователем. Получены навыки работы с нелинейными уравнениями.