Министерство образования Российской Федерации
Санкт-Петербургский государственный университет информационных технологий, государственный институт механики и оптики
Отчет о выполнении задания №13
Дисциплина: программирование и информатика
Выполнено:
Группа 1538
Санкт-Петербург
2003
1. Постановка задачи
Расчет переходного процесса в электрической сети, в которой присутствуют конденсаторы и резисторы, по неявной схеме Эйлера с применением LU-разложения матрицы для решения системы линейных уравнений. Цепь состоит из узлов, соединенных ветвями. В некоторых узлах заданы постоянные во времени потенциалы, в других же они в начальный момент времени равны нулю и меняются. Цепь имеет произвольную структуру, то есть любая пара узлов может быть соединена каким угодно числом параллельных ветвей, каждая из которых содержит или емкость, или сопротивление. Задача состоит в нахождении значений потенциалов в заданных узлах в заданные моменты времени.
2. Алгоритм решения задачи
Для решения задачи составляется система дифференциальных уравнений первого порядка с начальными условиями (равенство нулю потенциалов в некоторых узлах в начальный момент времени). Она составляется при помощи первого правила Кирхгофа – условия равенства суммы токов в каждом узле с неизвестным потенциалом. Получившуюся систему уравнений можно записать следующим образом:
, где A – квадратная матрица коэффициентов при производных потенциалов по времени, B - квадратная матрица коэффициентов при значениях потенциалов, D – столбец правых частей
Производную функции можно аппроксимировать следующим выражением:
, где fm+1 и fm – соответственно значения функции в (m+1)-ый и
m-ый моменты времени, а h – шаг моделирования.
Далее, выражая значения потенциалов на следующем шаге по времени через значения потенциалов на предыдущем шаге, получаем систему линейных уравнений:
, где Vm+1 – столбец значений потенциалов на следующем шаге, а G - квадратная матрица, вычисляемая следующим образом:
,
а F – столбец правых частей, вычисляемый так:
, где Vm – столбец значений потенциалов на текущем шаге по времени.
Начальные условия в этих обозначениях могут быть записаны так:
, где 0 – нулевой вектор размерности n.
Для решения этой систему применим метод LU-разложения матрицы. Так как матрица G неизменна на каждом шаге, то ее LU-разложение можно вычислить один раз, а потом на каждом шаге использовать полученное LU-разложение. LU-разложение представляет матрицу системы G в виде произведения нижне-треугольной матрицы L и верхне-треугольной матрицы U, после чего решение системы уравнений сводится к применению обратной и прямой подстановок. Для оценки погрешности применяется правило Рунге. Шаг по времени задается пользователем. Расчет ведется до тех пор, пока изменение хотя бы одного потенциала превышает по модулю задаваемое пользователем значение.
Алгоритм имеет временную сложность O(n3 + kn2), где n – число узлов с неизвестными потенциалами, k – количество шагов по времени до окончания переходного процесса.
Построение каждой вышеуказанной матрицы, вычисление LU-разложения и решение системы уравнений оформлены в виде отдельных процедур.
3. Формат входных и выходных данных
Имя входного файла – rcchain. in.
На первой строке входного файла находится целое число N0 - количество узлов с заданными неизменными во времени потенциалами. На второй строке – целое число N – количество узлов с неизвестными потенциалами. На третьей и четвертой строках находятся соответственно целые числа MR (количество ветвей, содержащих резисторы и соединяющих два узла с неизвестными потенциалами) и MR0 (количество ветвей, содержащих резисторы и соединяющих узел с известным потенциалом с узлом с неизвестным потенциалом). Пятая и шестая строки содержат соответственно целые числа целые числа MC (количество ветвей, содержащих конденсаторы и соединяющих два узла с неизвестными потенциалами) и MC0 (количество ветвей, содержащих конденсаторы и соединяющих узел с известным потенциалом с узлом с неизвестным потенциалом). Следующие N0 строк содержат известные значения потенциалов в узлах. Следующие MR строк содержат описание ветвей цепи, содержащих резисторы и соединяющих два узла с неизвестными потенциалами. Формат описания каждой ветви таков: I, K, C, где I и J – номера узлов с неизвестными потенциалами, которые соединяет данная ветвь, а C – емкость конденсатора. Далее в MR0 строках содержится описание ветвей цепи, соединяющих узел с известным потенциалом с узлом с неизвестным потенциалом и содержащих резистор. На каждой строке находятся три числа: I, J, R, где I – номер узла с известным потенциалом, J – номер узла с неизвестным потенциалом, R – сопротивление резистора. В следующих MC строках содержится описание ветвей, содержащих конденсатор и соединяющих два узла с неизвестным потенциалом. В следующих MC0 строках содержится описание ветвей, содержащих конденсатор и соединяющих узел с известным потенциалом и узел с неизвестным потенциалом. Формат описания ветви, содержащей конденсатор, аналогичен формату описания ветви, содержащей резистор.
Нумерация узлов с известными и неизвестными потенциалами независима. В следующей строчке содержатся два вещественных числа: H (шаг моделирования) и Eps (минимальное значение изменения потенциала) и одно целое KC (количество знаков после запятой выводящихся в ответе). Предпоследняя строка содержит число целое KS – оно определяет номера шагов, на которых будет выводиться результат (он выводится на шагах с номером, кратным KS). Последняя строка содержит число NN – количество узлов, значения потенциалов в которых нужно выводить – и NN чисел – номера этих узлов.
Имя выходного файла – rcchain. out.
В выходной файл выводится таблица значений потенциалов в заданных узлах в заданные моменты времени. На каждой строке выводится номер шага, ей соответствующий, и значение времени, соответствующее этому шагу, далее (на той же строке) выводятся значения потенциалов в заданных узлах на данный момент времени (в скобках выводится значение погрешности).
4. Пример результатов работы программы
Рассмотрим простейшую схему, содержащую резистор и конденсатор(представлена на рисунке).
На рисунке арабскими цифрами обозначены узлы с известными потенциалами, римскими – с неизвестными.
В узле 1 потенциал равен 100 вольтам.
Входной файл rcchain. in для данной схемы будет выглядеть так:
1
1
0
1
0
1
100
1 1 10
0.0000
100
1 1
Аналитическое решение этой задачи таково:
Результаты программного расчета дают:
Номер шага | Момент времени | Потенциал | Погрешность | Значение потенциала из аналитического решения |
#0 (time = 0..00000
#100 (time = 0..00451
#200 (time = 0..00817
#300 (time = 0..01110
#400 (time = 0..01339
#500 (time = 0..01515
#600 (time = 0..01645
#700 (time = 0..01736
#800 (time = 0..01796
#900 (time = 0..01828
#1000 (time = 0..01838
#1100 (time = 0..01829
Номер шага | Момент времени | Потенциал | Погрешность | Значение потенциала из аналитического решения |
#1200 (time = 0..01806
#1300 (time = 0..01770
#1400 (time = 0..01725
#1500 (time = 0..01672
#1600 (time = 0..01614
#1700 (time = 0..01552
#1800 (time = 0..01487
#1900 (time = 0..01420
#2000 (time = 0..01353
#2100 (time = 0..01285
#2200 (time = 0..01218
#2300 (time = 0..01152
#2400 (time = 0..01088
#2500 (time = 0..01025
#2600 (time = 0..00965
#2700 (time = 0..00907
#2800 (time = 0..00851
#2900 (time = 0..00797
#3000 (time = 0..00746
#3100 (time = 0..00698
#3200 (time = 0..00652
#3300 (time = 0..00608
#3400 (time = 0..00567
#3500 (time = 0..00528
#3600 (time = 0..00491
#3700 (time = 0..00457
#3800 (time = 0..00425
#3900 (time = 0..00394
#4000 (time = 0..00366
#4100 (time = 0..00339
#4200 (time = 0..00315
#4300 (time = 0..00291
#4400 (time = 0..00270
#4500 (time = 0..00250
#4600 (time = 0..00231
Из таблицы видно, что погрешность вычислений не превышает модуля разности между рассчитанным программно значением и полученным аналитически значением.
Также по результатам программного расчета можно построить график:
5. Список используемой литературы
Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы: построение и анализ, МЦНМО, Москва, 2001 Г. Корн, Т. Корн Справочник по математике для научных работников и инженеров, издательство «Наука», Москва, 1978