ТИТУЛЬНЫЙ ЛИСТ
Численное решение уравнения теплопроводности методом конечных разностей
к 2014
ОГЛАВЛЕНИЕ
Введение
1. Уравнение теплопроводности
1.1 Вывод уравнения теплопроводности
1.2 Условия однозначности
2. Метод конечных разностей
2.1 Формулировка метода из рядов Тейлора
2.2 Построение разностной схемы
3. Решение СЛАУ
3.1 Градиентные методы
3.1.1 Метод наискорейшего спуска
3.1.2 Метод сопряженных градиентов
4. Реализация
4.1 Организация
4.2 Результаты
Заключение
Список литературы
ВВЕДЕНИЕ
1. УРАВНЕНИЕ ТЕПЛОПРОВОДНОСТИ
Уравнение теплопроводности описывает распространение тепла в заданной области пространства в зависимости от времени.
Является параболическим дифференциальным уравнением в частных производных. В двумерном случае уравнение имеет вид:
∂u/∂t=α((∂^2 u)/(∂x^2 )+(∂^2 u)/(∂y^2 )) (1.1)
1.1 Вывод уравнения теплопроводности
Представим однородное тело и вычленим из него элементарный объем со сторонами dx, dy, dz (рисунок 1).
Рисунок 1. Контрольный объем в прямоугольной системе координат
Входящие потоки тепла, расположенные перпендикулярно к поверхностям обозначим как q_x, q_y, q_z. Потоки на противоположных поверхностях выразим из рядов Тейлора:
q_(x+dx)=q_x+(∂q_x)/∂x dx+⋯
q_(y+dy)=q_y+(∂q_y)/∂y dy+⋯
q_(z+dz)=q_z+(∂q_z)/∂z dz+⋯
(1.1.1)
Внутри тела так же могут быть внутренние источники тепла, если E_g>0 и стоки, если E_g<0:
E_g=q∙dx∙dy∙dz
Изменение внутренней энергии:
E_st=ρ∙C_p∙∂u/∂t∙(dxdydz)
E_in-E_out+E_g=E_st (1.1.2)
E_in=q_x+q_y+q_z (1.1.3)
E_out=q_(x+dx)+q_(y+dy)+q_(z+dz) (1.1.4)
Подставим уравнения (1.1.1), (1.1.3) и (1.1.4) в уравнение (1.1.2) и получим:
q_x+q_y+q_z-q_(x+dx)-q_(y+dy)-q_(z+dz)+qdxdydz==ρC_p ∂u/∂t(dxdydz) (1.1.5)
Подставим уравнения (1.1.1) в получившееся уравнение (1.1.5):
-(∂q_x)/∂x dx- (∂q_y)/∂y dy- (∂q_z)/∂z dz+q∙dxdydz=ρ∙C_p∙∂u/∂t∙(dxdydz) (1.1.6)
Потоки тепла выразим из закона Фурье:
q_x=-κdydz∂u/∂x
q_y=-κdxdz∂u/∂y
q_z=-κdxdy∂u/∂z
(1.1.7)
Подставив их в уравнение (1.1.6), получим уравнение теплопроводности в общем виде для трехмерного пространства:
∂/∂x (κ ∂u/∂x)+∂/∂y (κ ∂u/∂y)+∂/∂z (κ ∂u/∂z)+q=ρC_p ∂u/∂t
Введем коэффициент температуропроводности
α=κ/(ρC_p )
и опустим внутренние источники тепла. Получим уравнение теплопроводности в трехмерном пространстве без внутренних источников тепла:
∂u/∂t=α((∂^2 u)/(∂x^2 )+(∂^2 u)/(∂y^2 )+(∂^2 u)/(∂z^2 ))
1.2 Условия однозначности
Уравнение теплопроводности (формула ) описывает процесс в общем виде. Для ее применения к конкретной задаче необходимы дополнительные условия, называемые условиями однозначности. Данные условия включают в себя геометрические(форма и размеры тела), физические (физические свойства тела), временные(начальное распределение температуры) и граничные условия(описывают процесс теплообмена с окружающей средой).
Граничные условия можно разделить на три основных рода: (10 Ozisik Boundary value problems of heat conduction)
Граничные условия Дирихле: задано значение функции на границе.
T=f(r,t)
В случае задачи теплопроводности задают значения температуры на поверхности тела.
Граничные условия Неймана: задана нормальная производная функции на границе.
∂T/∂n=f(r,t)
Задают плотность теплового потока на поверхности тела.
Граничные условия Робена: задана линейная комбинация значения функции и ее производной на границе.
k ∂T/∂n+hT=f(r,t)
Описывают теплообмен между поверхностью тела и окружающей средой по закону Ньютона-Рихмана.
2. МЕТОД КОНЕЧНЫХ РАЗНОСТЕЙ
2.1 Формулировка метода из рядов Тейлора
Суть метода конечных разностей может быть выражена через определение производной функции u(x) в точке x=x_0:
∂u/∂x=lim┬(∆x→0)〖(u(x_0+∆x)-u(x_0))/∆x〗 (2.1.1)
Данная формула может стать подходящей заменой производной в случае, если функция u является непрерывной и ∆x является достаточно малой, но конечной величиной.
Представим теперь разложение в ряд Тейлора функции u(x) в окрестности точки x_0 в правом и левом направлениях:
u(x_0+∆x)=u(x_0 )+├ ∂u/∂x┤|_0 ∆x+├ (∂^2 u)/(∂x^2 )┤|_0 (∆x)^2/2!+├ (∂^3 u)/(∂x^3 )┤|_0 〖(∆x)〗^3/3!+⋯ (2.1.2)
u(x_0-∆x)=u(x_0 )-├ ∂u/∂x┤|_0 ∆x+├ (∂^2 u)/(∂x^2 )┤|_0 (∆x)^2/2!-├ (∂^3 u)/(∂x^3 )┤|_0 (∆x)^3/3!+⋯ (2.1.3)
Данные выражения формируют основу для конечно-разностной аппроксимации производной первого порядка ∂u/∂x в окрестности точки x_0. После перестановок в формулах (2.1.2) и (2.1.3) получим правую и левую конечно-разностные аппроксимации производной первого порядка соответственно:
├ ∂u/∂x┤|_0=(u(x_0+∆x)-u(x_0 ))/∆x+O(∆x) (2.1.4)
├ ∂u/∂x┤|_0=(u(x_0 )-u(x_0-∆x))/∆x+O(∆x) (2.1.5)
где O(∆x) обозначает ошибку аппроксимации, показывающую разность между производной и её конечно-разностным представлением.
Для правой конечной разности ошибка имеет вид:
O(∆x)≡∆x/2 u^ (x_0 )+〖(∆x)〗^2/6 u^ (x_0 )+⋯ (2.1.6)
Получим центральную конечную разность путем вычитания (2.1.5) из (2.1.4):
├ ∂u/∂x┤|_0=(u(x_0+∆x)-u(x_0-∆x))/2∆x-O(∆x)^2 (2.1.7)
Полученная аппроксимация имеет ошибку:
O(∆x)^2≡〖(∆x)〗^2/6 u^ (x_0 )+〖(∆x)〗^5/120 u^ (x_0 )+⋯
2.2 Построение разностной схемы
Для построения разностной схемы необходимо:
Совершить переход из области непрерывного изменения аргумента в её дискретный аналог.
Заменить производные их конечно-разностными аналогами.
Для замены области непрерывного изменения аргумента дискретным аналогом его изменения необходимо выбрать в данной области конечное множество точек – сетку. Тогда приближенное решение искать нужно будет только в узлах этой сетки. Функцию, определенную в узлах сетки будем называть сеточной функцией.( Самарский А. А. Введение в теорию разностных схем. – М. : Наука, 1971.)
Пусть функция u зависит от одной переменной x. Разобьем отрезок на N равных частей. Тогда шаг сетки ∆x=x_i-x_(i-1)=1/N . Узлами сетки будут точки деления x_i=i*h. Получили сетку, состоящую из множества всех её узлов.
Тогда аппроксимацию производной первого порядка в узле x_i можно произвести с помощью:
Правой конечной разности:
├ ∂u/∂x┤|_(x_i )=(u_(i+1)^ -u_i^ )/∆x (2.2.1)
Левой конечной разности:
├ ∂u/∂x┤|_(x_i )=(u_i^ -u_(i-1)^ )/∆x (2.2.2)
Центральной конечной разности:
├ ∂u/∂x┤|_(x_i )=(u_(i+1)^ -u_(i-1)^ )/2∆x
Произведем аппроксимацию производной второго порядка ├ (∂^2 u)/(∂x^2 )┤|_(〖 x〗_i ):
Для этого представим производную второго порядка функции u как производную первого порядка некоторой функции v:
∂u/∂x=v(x) ⟹ (∂^2 u)/(∂x^2 )=∂v/∂x
Аппроксимируем производную функции v в точке x_i правой конечной разностью (2.2.1):
├ ∂v/∂x┤|_(〖 x〗_i ) □(→) (v_(i+1)^ -v_i^ )/∆x= (├ ∂u/∂x┤|_(x_(i+1) ) - ├ ∂u/∂x┤|_(〖 x〗_i ) )/∆x
Аппроксимируем производные функции u левой конечной разностью (2.2.2):
├ ∂u/∂x┤|_(x_(i+1) )= (u_(i+1)^ -u_(i,j)^ )/∆x
├ ∂u/∂x┤|_(x_i )= (u_i^ -u_(i-1)^ )/∆x
├ (∂^2 u)/(∂x^2 )┤|_(x_i ) □(→) ((u_(i+1)^ -u_i^ )/∆x- (u_i^ -u_(i-1)^ )/∆x)/∆x = (u_(i+1)^ -2u_i^ +u_(i-1)^ )/(∆x)^2 (2.2.3)
В зависимости от выбора способа аппроксимации производной по времени можно получить два основных вида разностных схем:
Явная схема: значение узла на новом временном слое зависит только от значений узлов на предыдущем слое, то есть значение может быть вычислено явно из предыдущего слоя(рисунок 2). Данная разностная схема является устойчивой только при следующих условиях: (Strikwerda J. C. Finite difference schemes and partial differential equations. – Siam, 2004.)
Одномерный случай:
α ∂t/(∆x)^2 ≤1/2
Двумерный случай (h=∆x=∆y):
α ∂t/h^2 ≤1/4
Рисунок 2. Явная разностная схема
Неявная схема: значение узла на новом слое зависит и от соседних узлов на новом слое, и от значения на предыдущем слое(рисунок 3). Данная схема всегда является устойчивой, (1 Ozisik Finite difference methods in heat transfer) поэтому использовать ее.
Рисунок 3. Неявная разностная схема
Аппроксимируем частную производную функции u по переменной t в точке 〖t_n,x〗_i,y_j используя правую конечную разность (2.2.1):
├ ∂u/∂t┤|_(〖t_n,x〗_i,y_j )=(u_(i,j)^(n+1)-u_(i,j)^n)/∆t (2.2.4)
Аппроксимируем частную производную второго порядка функции u по переменной x в точке 〖t_(n+1),x〗_i,y_j с помощью (2.2.3):
├ (∂^2 u)/(∂x^2 )┤|_(x_i,y_j)^(n+1) □(→) (u_(i+1,j)^(n+1)-2u_(i,j)^(n+1)+u_(i-1,j)^(n+1))/(∆x)^2 (2.2.5)
Аналогично аппроксимируем частную производную второго порядка функции u по переменной y в точке 〖t_n,x〗_i,y_j и получаем:
├ (∂^2 u)/(∂y^2 )┤|_(x_i,y_j)^(n+1) □(→) (u_(i,j+1)^(n+1)-2u_(i,j)^(n+1)+u_(i,j-1)^(n+1))/(∆y)^2
(2.2.6)
Подставим получившиеся выражения (2.2.4), (2.2.5) и (2.2.6) в уравнение теплопроводности (1.1) и получим:
(u_(i,j)^(n+1)-u_(i,j)^n)/∆t=α((u_(i+1,j)^(n+1)-2u_(i,j)^(n+1)+u_(i-1,j)^(n+1))/(∆x)^2 +(u_(i,j+1)^(n+1)-2u_(i,j)^(n+1)+u_(i,j-1)^(n+1))/(∆y)^2 )
Элементы с n-ым шагом по времени перенесем вправо, элементы с (n+1)-ым шагом по времени перенесем влево:
u_(i,j)^(n+1)-∆tα((u_(i+1,j)^(n+1)-2u_(i,j)^(n+1)+u_(i-1,j)^(n+1))/(∆x)^2 +(u_(i,j+1)^(n+1)-2u_(i,j)^(n+1)+u_(i,j-1)^(n+1))/(∆y)^2 )==u_(i,j)^n
Для удобства будем считать, что ∆x=∆y=h:
u_(i,j)^(n+1)-∆tα((u_(i+1,j)^(n+1)+u_(i-1,j)^(n+1)+u_(i,j+1)^(n+1)+u_(i,j-1)^(n+1)-4u_(i,j)^(n+1))/h^2 )=u_(i,j)^n
Введем параметр:
s=∆tα/h^2
u_(i,j)^(n+1)-s(u_(i+1,j)^(n+1)+u_(i-1,j)^(n+1)+u_(i,j+1)^(n+1)+u_(i,j-1)^(n+1)-4u_(i,j)^(n+1) )=u_(i,j)^n
-su_(i+1,j)^(n+1)-su_(i-1,j)^(n+1)-su_(i,j+1)^(n+1)-su_(i,j-1)^(n+1)+(1+4s)u_(i,j)^(n+1)=u_(i,j)^n (2.2.7)
Запишем полученную разностную схему (2.2.7) в виде СЛАУ
Ax=b (2.2.8)
Где
(2.2.9)
Координаты узлов из двумерных переведем в одномерные в лексикографическом порядке сверху вниз, слева направо:
(2.2.10)
(2.2.11)
3. Решение СЛАУ
3.1 Градиентные методы
Чтобы найти решение СЛАУ(2.2.8) с положительно-определенной матрицей (2.2.9), достаточно найти набор значений x_1,x_2,…,x_n, при которых соответствующая квадратичная форма достигает своего минимального значения.
Ввиду положительной определенности матрицы A, график квадратичной формы имеет вид эллиптического параболоида с ветвями образующих парабол вверх (рисунок 4).
Рисунок 4. График квадратичной формы с положительно-определенной матрицей
Квадратичная форма имеет вид:
f(x)=1/2 x^T Ax-b^T x+c (3.1.1)
где b∈R^n - вектор правой части СЛАУ
x∈R^n - вектор неизвестных
A∈R^(n×n) – симметричная, положительно-определенная матрица
Симметричная матрица A является положительно-определенной, если
x^T Ax>0 ∀x∈Ω (3.1.2)
Для соблюдения условия (3.1.2) необходимо и достаточно, чтобы все главные миноры матрицы A были положительны. (Gilbert G. T. Positive definite matrices and Sylvesters criterion //American Mathematical Monthly. – 1991. – С. 44-46.)
Для того чтобы показать что x минимизирующий f(x) также служит решением СЛАУ возьмем градиент квадратичной формы (3.1.1) и приравняем его нулю:
f^ (x)=1/2 A^T x+ 1/2 Ax-b=0
Ввиду симметричности матрицы A (A^T=A) получим:
f^ (x)=Ax-b=0
Ax=b
В градиентных методах направления спуска выбираются исходя от градиента функции в текущей точке. Градиентные методы отличаются друг от друга способом выбора направления спуска и длиной шага. В данной работе будут рассмотрены два градиентных метода: метод наискорейшего спуска и метод сопряженных градиентов.
3.1.1 Метод наискорейшего спуска
В методе наискорейшего спуска из произвольной начальной точки x_0 выполняются последовательные спуски к точкам x_1,x_2… до тех пор, пока мы не приблизимся достаточно близко к минимуму (рисунок 5).
Рисунок 5. Контурный график квадратичной формы с изображенными линиями спуска
Рис () (Refsnæs R. H. A brief introduction to the conjugate gradient method)
Направление спусков выбирается в направлении наискорейшего убывания функции в данной точке (то есть по направлению антиградиента)
-f^ (x_i )=b-Ax_i
Каждая следующая точка x_(i+1) находится как:
x_(i+1)=x_i+αr_i
где
x_i- точка, из которой выполняется спуск
α-длина шага
r_i - антиградиент в точке x_0
r_i=b-Ax_i (3.1.1.1)
Из уравнения (3.1.1.1) видно, что вектор r_i также является невязкой. Его можно использовать в условии остановки последовательности спусков, когда относительная невязка ‖r‖/‖b‖ становится меньше заданного числа.
Длина шага α выбирается из учета того, что спускаться нужно только до тех пор, пока функция на линии, соответствующей выбранному направлению (3.1.1.1) убывает. Представим функцию g(x) как параболу, образованную пересечением параболоида и вертикальной плоскости (рисунок 6).
Рисунок 6. Пересечение графика квадратичной формы с вертикальной плоскостью, образующее параболу g(x) на которой необходимо найти минимум.
Нужно найти такую α, чтобы f(x) достигала на ней своего минимума.
d/dα f(x_(i+1) )=f^ (x_(i+1) )^T d/dα x_(i+1)=f^ (x_(i+1) )^T r_i
f^ (x_(i+1) )^T r_i=0 (3.1.1.2)
Из формулы (3.1.1.2) следует, что направление каждого последующего спуска должно быть ортогонально направлению предыдущего спуска.
Теперь путем подстановок и преобразований получим длину шага α: (Shewchuk J. R. An introduction to the conjugate gradient method without the agonizing pain. – 1994.)
r_(i+1)^T r_i=0
(b-Ax_(i+1) )^T r_i=0
(b-A(x_i+αr_i))^T r_i=0
(b-Ax_i )^T r_i-α(Ar_i )^T r_i=0
(b-Ax_i )^T r_i=α(Ar_i )^T r_i
r_i^T r_i=αr_i^T (Ar_i )
α=(r_i^T r_i)/(r_i^T Ar_i )
В итоге, метод наискорейшего спуска выглядит следующим образом:
r_i=b-Ax_i (3.1.1.3)
α_i=(r_i^T r_i)/(r_i^T Ar_i )
x_(i+1)=x_i+α_i r_i (3.1.1.4)
Приведенный выше алгоритм требует два умножения матрицы на вектор для каждой итерации. Чтобы избавиться от одного матрично-векторного произведения (3.1.1.3) в уравнении (3.1.1.4) обе части умножим на (–A) и прибавим b:
b-Ax_(i+1)=b〖-Ax〗_i-α_i Ar_i
r_(i+1)=r_i-α_i Ar_i
Получили следующий алгоритм:
r_0←b-Ax_0
Для i от 0 до maxiter-1:
α_i=(r_i^T r_i)/(r_i^T Ar_i )
x_(i+1)=x_i+α_i r_i
r_(i+1)=r_i-α_i Ar_i
Если ‖r‖/‖b‖ <ε
Выход из цикла
Недостатком метода наискорейшего спуска является медленная сходимость, если квадратичная функция имеет «овраг»: спуск может пойти мелкими «зигзагами» вдоль оврага, потратив на это большое количество шагов.
Метод сопряженных градиентов
В отличие от метода наискорейшего спуска, где спуск часто производится по тем же направлениям, которые использовались ранее, в методе сопряженных градиентов спуск производится по сопряженным направлениям без их повторного использования. Данный метод позволяет минимизировать квадратичную функцию за n шагов (если не учитывать ошибки округления).( Nocedal J., Wright S. J. Conjugate gradient methods. – Springer New York, 2006. – С. 101-134.)
Множество векторов – направлений спуска d_0,d_1,… ,d_(n-1) называются сопряженными по отношению к матрице A (или A - ортогональными), если
d_i^T Ad_j=0,i≠j
Особенностью метода сопряженных градиентов состоит в способе генерации сопряженных векторов: для вычисления вектора d_i нужно знать только предыдущий вектор d_(i-1).
Каждое направление спуска вычисляется как линейная комбинация направления наискорейшего спуска и направления спуска на предыдущем шаге:
d_i=-r_i+β_i d_(i-1)
где β_i находится из условия сопряженности d_(i-1)^T Ad_i=0:
β_i=(r_i^T Ad_(i-1))/(d_(i-1)^T Ad_(i-1) )=(r_i^T r_i)/(r_(i-1)^T r_(i-1) )
В итоге получили алгоритм метода сопряженных градиентов:
r_0←b-Ax_0
d_0←r_0
Для i от 0 до maxiter-1:
α_i←(r_i^T r_i)/(d_i^T Ad_i )
x_(i+1)←x_i+α_i d_i
r_(i+1)←r_i-α_i Ad_i
Если ‖r_(i+1) ‖/‖b‖ <ε
Выход из цикла
β_(i+1)←(r_(i+1)^T r_(i+1))/(r_i^T r_i )
d_(i+1)←r_(i+1)+β_(i+1) d_i
4. РЕАЛИЗАЦИЯ
4.1 Организация
Основными вычислениями, которые целесообразно распараллелить в алгоритмах () и () являются матричные и векторные операции: умножение матрицы на вектор, сумма векторов и скалярное произведение вектора.
Вместо хранения матрицы A будем использовать функцию, возвращающую её элемент:
double A(int i, int j, int xys, double s)
{
if (i == j)
return 1 + 4 * s;
if (i + 1 == j || i - 1 == j || i + xys == j || i - xys == j)
return -s;
return 0;
}
Параллелизация скалярного произведения (рисунок 7):
С помощью MPI_Scatter разбиваем оба вектора на куски и рассылаем их соответствующим процессам.
Каждый процесс вычисляет свою часть скалярного произведения.
С помощью MPI_Reduce выполняем редукцию суммированием, получая результат скалярного произведения в нулевом процессе.
Рисунок 7. Параллелизация скалярного произведения
Параллелизация умножения матрицы на вектор (рисунок 8):
Так как значения элементов матрицы мы берем из функции, которая доступна всем процессам, то рассылать нужно только вектор с помощью MPI_Broadcast.
Каждый процесс вычисляет свой кусок результирующего вектора
Собираем куски вектора в один на нулевом процессе с помощью MPI_Gather.
Рисунок 8. Параллелизация умножения матрицы на вектор
Параллелизация суммирования векторов (рисунок 9):
С помощью MPI_Scatter разбиваем оба вектора на куски и рассылаем их соответствующим процессам.
Каждый процесс вычисляет свой кусок результирующего вектора
Собираем куски вектора в один на нулевом процессе с помощью MPI_Gather.
Рисунок 9. Параллелизация суммирования векторов
4.2 Результаты
Intel Core i5-3470 @ 3.20 GHz
Метод Кол-во итераций 1 процесс 2 процесса 4 процесса
Время (с) Время (с) Ускорение Время (с) Ускорение
SD 2563 81.263 43.867 1.852 27.051 3.004
CG 85 2.805 1.560 1.798 0.999 2.807
Количество узлов сетки: 64 x 64
ε=0.001
ЗАКЛЮЧЕНИЕ
Список литературы
Ozisik N. Finite difference methods in heat transfer. – CRC press, 1994.
Ozisik M. N. Boundary value problems of heat conduction. – Courier Dover Publications, 2013.
Refsnæs R. H. A brief introduction to the conjugate gradient method – 2009.
Gilbert G. T. Positive definite matrices and Sylvesters criterion //American Mathematical Monthly. – 1991. – С. 44-46.
Shewchuk J. R. An introduction to the conjugate gradient method without the agonizing pain. – 1994.
Nocedal J., Wright S. J. Conjugate gradient methods. – Springer New York, 2006. – С. 101-134.
Самарский А. А. Введение в теорию разностных схем. – М. : Наука, 1971.
Strikwerda J. C. Finite difference schemes and partial differential equations. – Siam, 2004.
Gropp W., Lusk E., Skjellum A. Using MPI: portable parallel programming with the message-passing interface. – MIT press, 1999. – Т. 1.
Численное решение уравнения теплопроводности методом конечных разностей
Курсовая работа по предмету «Физика»