Нахождение параметров линейной функции

Введение

 

Основными целями лабораторного практикума по курсу "Информатика. Основы вычислительной математики" являются:

- закрепление знаний по теоретическим основам использования методов вычислительной математики для анализа математических моделей технических и экономических объектов;

- получение практических навыков работы на компьютерах, отладки и тестирования программ.

Методические указания являются третьей частью серии методических указаний по курсу «Информатика» для студентов заочного обучения. Они содержат описание ряда численных методов, примеры решения конкретных задач и индивидуальные задания для самостоятельных лабораторных работ. В указаниях рассмотрены следующие темы: приближенное решение нелинейных уравнений; решение систем линейных алгебраических уравнений; решение обыкновенных дифференциальных уравнений; аппроксимация функций с помощью метода наименьших квадратов; линейное программирование.

Для реализации численных методов в процессе решения поставленных задач предполагается использование среды программирования Turbo Pascal или процессора электронных таблиц MS Excel.

 

 

Требования к оформлению лабораторных работ

 

Лабораторные работы оформляются в тетради в виде отчета, который должен содержать:

1. Номер варианта

2. Название лабораторной работы.

3. Задание.

4. Расчетная часть:

a. Краткое теоретическое описание метода.

b. Ручной расчет для двух-трёх шагов.

c. Текст программы или описание хода решения задачи с использованием MS Excel.

d. Введенные исходные данные и результаты расчетов.

5. Вывод.

 

 

1. Приближенное решение нелинейных уравнений

Пусть дано уравнение с одним неизвестным

, (1.1)

где - заданная алгебраическая или трансцендентная функция.

Решить уравнение - значит найти все его корни, то есть те значения , которые обращают уравнение в тождество, или доказать, что корней нет.

В общем случае не существует формул, по которым определяются точные значения корней уравнения (1.1). Для отыскания корней используют приближенные методы, при этом корни находятся с некоторой заданной точностью . Это означает, что если - точное значение корня уравнения, а - его приближенное значение с точностью , то . Если корень найден с точностью , то принято писать .

Будем предполагать, что уравнение (1.1) имеет лишь изолированные корни, то есть для каждого корня существует окрестность, не содержащая других корней этого уравнения.

Приближенное решение уравнения состоит из двух этапов:

1. Отделение корней, то есть нахождение интервалов из области определения функции , в каждом из которых содержится только один корень уравнения (1).

2. Уточнение корней до заданной точности.

Отделение корней можно проводить графически и аналитически.

Для того, чтобы графически отделить корни уравнения (1.1), строят график функции . Абсциссы точек его пересечения с осью Ox есть действительные корни уравнения (рис. 1). Практически бывает удобнее заменить уравнение (1.1) равносильным ему уравнением

, (1.2)

где и - более простые функции, чем . Абсциссы точек пересечения графиков функций и дают корни уравнения (1.2), а значит и исходного уравнения (1.1) (рис.2).

Аналитическое отделение корней основано на следующей теореме: если непрерывная на отрезке функция принимает на концах отрезка значения разных знаков, т.е. , то внутри этого отрезка находится хотя бы один корень уравнения ; если при этом производная со-

 

Функция называется алгебраической, если для получения её значения нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Примеры трансцендентных функций - показательная, логарифмическая, тригонометрические, обратные тригонометрические.

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

 

 

Рис. 1. Рис. 2.

 

Уточнение корней заключается в сужении интервала изоляции корня и выполняется одним из специальных методов. Рассмотрим самый простой из них - метод половинного деления.

рень. Если , то в качестве нового отрезка изоляции корня выбираем ту половину или , на концах которой принимает значения разных знаков. Другими словами, если , то корень принадлежит отрезку , если - отрезку . Полученный отрезок снова делим пополам, находим ,

Пусть корень отделён и принадлежит отрезку . Находим середину отрезка по формуле (рис.3). Если , то с - искомый ко-

 

Рис. 3.

 

 

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

Пример. Пусть требуется решить уравнение с точностью =0,0001. Отделим корень графически. Для этого преобразуем урав-

(рис. 4). Из рисунка видно, что абсцисса точки пересечения этих графиков принадлежит отрезку . Подтвердим аналитически правильность нахождения отрезка изоляции корня. Для отрезка имеем: ; . Следовательно, корень отделён правильно.

нение к виду и построим графики функций и

Рис. 4.

 

Уточнение корня выполним методом половинного деления.

Первый шаг.

Корень принадлежит отрезку

Второй шаг.

Корень принадлежит отрезку

Третий шаг.

Корень принадлежит отрезку

Сведём результаты вычислений в таблицу.

 

 

Таблица 1.

a	b		c	f(a)	f(c)
			0.5	0.5	-0.57436	<0
	0.5	0.5	0.25	0.5	-0.07951	<0
	0.25	0.25	0.125	0.5	0.19905	>0
0.125	0.25	0.125

Дальнейшие вычисления проведём с помощью программы.

program equation; {Решение уравнения методом половинного деления}

Uses crt;

Var

a,b: real; { Концы отрезка }

c: real; { Середина отрезка }

e: real; { Точность }

function f(x: real): real;

Begin

f: = sqr(x-1) - 0.5*exp(x); { Функция f(x) }

End;

Begin

writeln (' Введите концы отрезка: ');

write (' a = '); readln (a);

write (' b = '); readln(b);

write (' Введите точность e = '); readln (e);

writeln(' Результат: ');

while abs (b - a) > 2*e do

Begin

c: = (a + b) / 2;

if f(c) = 0 then

Begin

writeln(' c = ', c: 8: 6, ' f(c) = ', f(c): 8: 6);

Readln;

Exit;

End;

if f(a) * f(c) < 0 then b: = c else a: = c;

End;

c: = (a + b) / 2;

writeln(' c = ', c: 8: 6, 'f(c) = ', f(c): 8: 6);

Readln;

End.

 

Были введены следующие значения: a = 0, b = 1, e = 0.0001.Получены результаты: с = 0.213287; f (c) = 0.000047.

Ответ: корень уравнения равен 0,2133 0,0001.

Задания. Найти корень уравнения (если корней несколько, взять наименьший положительный) с точностью 0,0001.

Таблица 2.

№ варианта	Уравнение	№ варианта	Уравнение

 

 

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

Системы линейных алгебраических уравнений (СЛАУ) широко используются во многих областях прикладной математики. Оставляя за рамками данной работы вопросы теории линейных систем, отметим, что некоторые СЛАУ могут вообще не иметь решения или иметь бесконечное множество решений. В дальнейшем мы будем рассматривать только системы, имеющие единственное решение.

В общем виде система из n уравнений с n неизвестными выглядит так:

(2.1)

Таким образом, даны квадратная матрица коэффициентов при неизвестных { a_ij }, i, j = 1, 2, …, n, и вектор-столбец свободных членов (правых частей уравнений) { b_i }, i = 1, 2, …, n. В результате решения требуется определить n неизвестных x₁, x₂, …, x_n, которые удовлетворяют одновременно всем уравнениям системы.

Все методы решения СЛАУ делятся на две группы – прямые и итерационные. Прямые методы дают решение после выполнения конечного числа операций. Эти методы достаточно универсальны, но в ряде случаев полученное решение не является достаточно точным. Итерационные методы используют последовательные приближения (итерации) к искомому результату. Они позволяют получить решение с любой заданной точностью, но при их использовании заранее неизвестно количество предстоящих итераций, более того, итерационные методы в некоторых случаях вообще не дают решения.

В данном пособии мы рассмотрим по одному методу из каждой группы.

Метод Гаусса

Суть метода состоит в следующем. Вначале квадратную матрицу коэффициентов при неизвестных преобразуют в верхне-треугольную матрицу (прямой ход). Для этого сначала первое неизвестное исключают из второго и последующих уравнений системы, затем второе неизвестное исключают из третьего и последующих уравнений и так далее. Таким образом, в последнем уравнении остается только одно неизвестное. Для реализации прямого хода используют следующие известные правила:

- любое уравнение системы можно умножить на постоянный коэффициент;

- можно сложить два любых уравнения системы и результат записать вместо одного из этих уравнений.

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

Рассмотрим применение метода Гаусса на примере. Пусть имеем такую систему из трех уравнений:

 

 

Для исключения первого неизвестного из второго уравнения умножим первое уравнение на (-a₂₁/a₁₁), т.е. на –0,5. Первое уравнение примет вид

-2x₁ – 0,5x₂ + 0,5x₃ = -1,5.

Сложив его со вторым уравнением исходной системы (2.2), получим

– 2,5x₂ + 1,5x₃ = -0,5.

Можно заметить, что неизвестное x₁ в данном уравнении отсутствует.

Для исключения первого неизвестного из третьего уравнения системы (2.2) умножим первое уравнение этой системы на (-a₃₁/a₁₁), т.е. на –0,25. Первое уравнение примет вид

-x₁ – 0,25x₂ + 0,25x₃ = -0,75.

Сложив его с третьим уравнением исходной системы (2.2), получим

-1,25x₂ + 2,25x₃ = 4,25.

Можно заметить, что и в этом уравнении неизвестное x₁ отсутствует.

Таким образом, система (2.2) примет вид

4x₁ + x₂ – x₃ = 3

-2,5x₂ + 1,5x₃ = -0,5 (2.3)

-1,25x₂ + 2,25x₃ = 4,25

Теперь исключим неизвестное x₂ из третьего уравнения системы (2.3), сложив его со вторым уравнением системы (2.3), умноженным на –0,5. Получим систему

4x₁ + x₂ – x₃ = 3

-2,5x₂ + 1,5x₃ = -0,5 (2.4)

1,5x₃ = 4,5

Прямой ход закончен, исходная матрица коэффициентов приведена к верхне-треугольному виду. В третьем уравнении системы (2.4) присутствует только неизвестное x₃. Теперь легко осуществить обратный ход, т.е. вычислить неизвестные. Из третьего уравнения вычислим x₃, далее его значение подставим во второе уравнение и вычислим x₂, а затем из первого уравнения найдём x₁. Получим ответ: x₁ = 1; x₂ = 2; x₃ = 3. Задача решена.

Программа для решения СЛАУ методом Гаусса может иметь такой вид:

program SLAU1; {Решение системы линейных уравнений методом Гаусса}

Uses crt;

const n=3;

var a:array [1..n,1..n] of real;

b,x: array [1..n] of real;

i,j,k: integer; c,s: real;

Begin

{Ввод исходных данных}

for i:=1 to n do

Begin

writeln (‘Введите коэффициенты уравнения’,i);

for j:=1 to n do read (a[i,j]);

writeln (‘Введите свободный член уравнения’,i);

readln (b[i]);

End;

{Прямой ход}

for k:=1 to n-1 do

Begin

for i:=k+1 to n do

Begin

c:=-a[i,k]/a[k,k]; a[i,k]:=0;

for j:= k+1 to n do a[i,j]:=a[i,j]+c*a[k,j];

b[i]:=b[i]+c*b[k];

End;

End;

{Oбратный ход}

x[n]:=b[n]/a[n,n];

for i:=n-1 downto 1 do

Begin

s:=0;

for j:=i+1 to n do s:= s+a[i,j]*x[j];

x[i]:=(b[i]-s)/a[i,i];

End;

{Вывод результатов}

writeln (‘Решение системы’);

for i:=1 to n do write (x[i]:8:4);

Writeln;

End.

Метод Гаусса-Зейделя.

Данный метод является одним из самых распространенных итерационных методов решения СЛАУ, поскольку он отличается простотой и легкостью программирования. Рассмотрим его суть. Допустим, диагональные коэффициенты исходной матрицы { a_ij }отличны от нуля (в противном случае можно переставить местами уравнения исходной системы). Представим исходную систему (2.1) в следующем виде:

(2.5)

 

Если теперь задать для неизвестных их начальные приближенные значения , то система (2.5) позволяет вычислить более точные значения неизвестных на первом шаге (на первой итерации):

(2.6)

 

Используя найденные значения неизвестных, можно еще более уточнить их на второй итерации:

(2.7)

 

и так далее.

В данном методе для нахождения значения i-го неизвестного на каждой итерации используются значения предыдущих неизвестных, уже найденные на данной итерации. Общую формулу определения i-го неизвестного на k-й итерации для системы n уравнений можно записать так:

i = 1, 2, …, n; k = 1, 2, …

(2.8)

Итерационный процесс продолжается до тех пор, пока все значения x_i^(k), не станут достаточно близкими к x_i^(k-1). Близость этих значений можно охарактеризовать максимальной абсолютной величиной их разности d. Тогда при заданной точности вычислений e > 0 критерий окончания итерационного процесса можно записать в виде

.

(2.9)

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

Доказано, что для сходимости итерационного процесса достаточно, чтобы модули диагональных коэффициентов для каждого уравнения были не меньше суммы модулей всех остальных коэффициентов:

,

(2.10)

При этом хотя бы для одного уравнения неравенство (2.10) должно выполняться строго.

В качестве примера рассмотрим решение методом Гаусса-Зейделя системы (2.2). Заметим, что достаточное условие сходимости итерационного процесса (2.10) для этой системы соблюдается. Запишем исходную систему в виде

 

В качестве начальных приближений возьмем нули, т.е. примем x₂⁽⁰⁾ = x₃⁽⁰⁾= 0.

Найдем значения неизвестных на первой итерации:

 

 

 

 

Далее произведем вторую итерацию:

 

Производя аналогично третью и последующие итерации, найдем:

x₁⁽³⁾ = 0,984; x₂⁽³⁾ = 1,981; x₃⁽³⁾ = 2,953;

x₁⁽⁴⁾ = 1,015; x₂⁽⁴⁾ = 1,992; x₃⁽⁴⁾ = 2,988;

x₁⁽⁵⁾ = 0,999; x₂⁽⁴⁾ = 1,993; x₃⁽³⁾ = 2,997.

Нетрудно заметить, что разности между значениями соответствующих неизвестных в процессе итераций убывают, следовательно, процесс решения сходящийся, что и следовало ожидать. Если принять точность вычислений e = 0,02, то итерации следует закончить. При увеличении заданной точности вычисления корней, число итераций возрастает, например, при e = 0,00001 следует выполнить 11 итераций, а результат будет x₁⁽¹¹⁾ = 1,000000; x₂⁽¹¹⁾ = 1,999998; x₃⁽¹¹⁾ = 2,999999.

Программа для решения СЛАУ методом Гаусса-Зейделя приведена ниже. Поскольку при некорректной постановке задачи количество итераций может стать излишне большим, в программе предусмотрено прекращение итерационного процесса при превышении заранее заданного предельного числа итераций.

program SLAU2; {Решение системы методом Гаусса-Зейделя}

Label 1,2,3;

const n=3;

var a:array [1..n,1..n] of real;

b,x:array [1..n] of real;

i,j,k,m:integer;

e,s,d,d1,c:real;

Begin

{Ввод исходных данных}

for i:=1 to n do

Begin

writeln (‘Введите коэффициенты уравнения’,i);

for j:=1 to n do read (a[i,j]);

writeln (‘Введите свободный член уравнения’,i);

readln (b[i]);

End;

writeln ('Введите точность');readln (e);

writeln ('Введите допустимое кол-во итераций');readln (m);

for i:=2 to n do x[i]:=0;

{Решение системы}

k:=1;

Repeat

d1:=0;

for i:=1 to n do

Begin

s:=0;

for j:=1 to n do

Begin

if i=j then goto 1;

s:=s+a[i,j]*x[j];

End;

c:=(b[i]-s)/a[i,i];

d:=abs(c-x[i]);

if d1<d then d1:=d;

x[i]:=c;

End;

k:=k+1;

if k>m then goto 2;

until d1<e;

{Вывод результатов}

writeln (‘решение системы’);

for i:=1 to n do write (x[i]:8:4);

Writeln; goto 3;

2: writeln ('Количество итераций выше допустимого');

End.

 

Задания. Решить систему линейных алгебраических уравнений.

Таблица 3.

 

№ варианта	Система	Метод решения
		Метод Гаусса
		Метод Гаусса-Зейделя ()
		Метод Гаусса
		Метод Гаусса-Зейделя ()
		Метод Гаусса
		Метод Гаусса-Зейделя ()
		Метод Гаусса
		Метод Гаусса-Зейделя ()
		Метод Гаусса
		Метод Гаусса-Зейделя ()

 

3. Аппроксимация функций с помощью метода

Наименьших квадратов

Метод наименьших квадратов применяется при обработке результатов эксперимента для аппроксимации (приближения) экспериментальных данных аналитической формулой. Конкретный вид формулы выбирается, как правило, из физических соображений. Такими формулами могут быть: , и другие.

Сущность метода наименьших квадратов состоит в следующем. Пусть результаты измерений представлены таблицей:

Таблица 4.

			…
			…

Будем считать, что вид аппроксимирующей (приближающей) зависимости выбран, и её можно записать в виде

-1, (3.1)

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

(3.2)

то есть суммa квадратов отклонений искомой аналитической функции от экспериментальной зависимости должна быть минимальна.

Заметим, что функция Q называется невязкой.

 

-экспериментальные точки -отклонения … … Рис. 5.

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

(3.3)

 

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

Нахождение параметров линейной функции

Пусть экспериментальные данные надо представить линейной функцией . Требуется подобрать такие значения и , для которых функция

(3.4)

будет минимальной. Необходимые условия минимума функции (3.4) сводятся к системе уравнений

После преобразований получаем систему двух линейных уравнений с двумя неизвестными

, (3.5)

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