2.6 Варианты заданий к лабораторной работе №2

Найдите корни уравнения используя методы решения нелинейных уравнений.

1. 6.

2. 7.

3. 8.

4. 9.

5. 10.

Содержание отчета

Отчет должен содержать:

1. титульный лист;

2. постановку задачи (согласно варианту);

3. краткое описание методов расчета нелинейных уравнений;

4. программную реализацию данных методов;

5. выводы о проделанной работе.

Контрольные вопросы и задания

1. Какие методы решения нелинейных уравнений вы знаете?

2. Какой из методов решения нелинейных уравнений, в вашем случае, оказался наиболее быстрым и медленным?

3. Дайте описание метода половинного деления.

4. Запишите расчетную формулу метода хорд.

5. Запишите расчетную формулу метода секущих.

6. Запишите расчетную формулу метода Ньютона.

7. Сформулируйте теорему Больцано–Коши.

8. Решите нелинейное уравнение.

9. Запишите формулу для расчета погрешности метода половинного деления.

10. Запишите формулу для расчета погрешности метода Ньютона.

3 Прямые методы решения систем линейных алгебраических уравнений

Прямые методы теоретически позволяют за конечное число операций (действий) найти «точное» решение системы. Однако, в условиях вычислений на компьютерах, имеющих конечную разрядную сетку, прямые методы позволяют найти реально лишь приближенное решение системы, ввиду наличия погрешностей округления. Примерами прямых методов, рассматриваемых ниже, являются метод Гаусса и его модификации.

3.1 Метод Гаусса для решения систем линейных алгебраических уравнений.

Рассмотрим систему линейных алгебраических уравнений

Ах = b ,

(3.1)

где х = (х₁, х₂, … х_n)^Т – вектор неизвестных;

b = (b₁, b₂, … b_n)^Т – вектор свободных членов;

А = , i,j = 1,2,…,n – невырожденная матрица размерами n  n.

В силу невырожденности матрицы А (det A  0) для однородной системы уравнений с вектором правых частей b = (0, 0,…,0)^T имеем единственное тривиальное решение х=(0,0,…,0)^T. Для неоднородной системы имеем единственное решение х = А^-1b, где А^-1 – матрица, обратная А.

Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка 2/3 n³. Он используется для решения СЛАУ с n  10²-10⁴.

Объединим матрицу А и вектор b в расширенную матрицу.

размерами n  (n+1), которая содержит всю известную информацию о системе (3.1).

Опишем вначале прямой ход, первый шаг которого состоит в обнулении всех элементов первого столбца матрицы А⁽⁰⁾, кроме того, что находится в первой строке.

Введем обозначение

а_i = (a_i1, a_i2, … a_in, b_i).

C матрицей А⁽⁰⁾ можно обращаться так же, как с исходной системой (3.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число.

Найдем ненулевой элемент в первом столбце матрицы А⁽⁰⁾. Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица А – вырожденная. Пусть а_r1  0, тогда поменяем местами строки номера r и 1. Если r = 1, то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера i, i = 2, … , n первую строку, умноженную на число f_i, где

.

В результате все элементы i-ой строки изменят свои значения и станут равными

(3.2)

Здесь мы предполагаем, что хотя перестановка строк и могла состояться, однако нумерация элементов матрицы А⁽⁰⁾ осталась прежней. Введем обозначения

(3.3)

С учетом введенных обозначений (3.2) и (3.3) матрица А⁽⁰⁾ преобразуется к матрице А⁽¹⁾ и станет равной

.

(3.4)

Тот же алгоритм может быть применен на втором шаге к (n-1)  n матрице, которая получается из А⁽¹⁾, если убрать в ней первую строку и первый столбец. Применение этого алгоритма j раз приводит к матрице А^(j)

В матрице А^(j) полученные нули располагаются в столбцах с номерами от 1 до j ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма. В результате применения алгоритма n раз система (3.1), в конечном счете, преобразуется в систему вида

R x = C

(3.5)

где R – верхняя (правая) треугольная матрица, т.е.

.

(3.6)

Значения неизвестных можно вычислить из (3.6) по формулам

xn = cn / rnn, .

(3.7)

Процесс приведения системы (3.1) к треугольному виду (3.6) называется прямым ходом, а нахождение неизвестных по формулам (3.7) называется обратным ходом.

Произведем подсчет числа арифметических операций в методе Гаусса. Число арифметических операций, необходимое для реализации прямого хода в методе Гаусса для решения систем уравнений порядка n, равно

.

(3.8)

При обратном ходе

QII = n(n – 1) = n2 – n.

(3.9)

Из формул (3.8) и (3.9) получаем оценку общего числа арифметических действий

.

Если имеется р систем вида (3.1) с одинаковыми матрицами А и разными правыми частями ,то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над р правыми частями (матрицей порядка np). Количество арифметических операций, необходимое для реализации прямого метода Гаусса с учетом (3.8) и (3.9), есть

.

Количество арифметических операций, необходимое для реализации р обратных ходов (для р систем) методом Гаусса, есть Q_IIp= p(n² – n). Откуда следует, что общее количество арифметических операций, необходимое для реализации р систем с разными правыми частями, равно

.