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

Размещено на http://allbest.ru/

Міністерство освіти та науки України

Житомирський державний технологічний університет

Звіт до розрахункової роботи

з предмету «Емпіричні методи програмної інженерії»

Виконав: К. Д. Саєцький

Перевірив: В. О. Скачков

Житомир 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,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

Находим x6: 1,628991

Находим 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

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,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

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

Находим 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. Дополнения

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;

}

}

Вывод

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

Размещено на Allbest.ru