Matemática Numérica III

3 Sistemas Não Lineares e Otimização 3 Sistemas Não Lineares e Otimização 3.2 Problemas de Minimização

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

3.1 Sistemas Não-Lineares

Em revisão

Consideramos o seguinte problema: dada a função $F:D\subset\mathbb{R}^{n}\to\mathbb{R}^{n}$ encontrar $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ tal que

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}F(\boldsymbol% {x}^{*})=0.

(3.1)

Salvo explicitado ao contrário, assumiremos que $F\in C^{1}(D)$ , i.e. $F$ é uma função continuamente diferenciável no domínio computacional $D\subset\mathbb{R}^{n}$ .

Vamos, denotar por $J_{F}(\boldsymbol{x})=[\jmath_{i,j}(\boldsymbol{x})]_{i,j=1}^{n,n}$ a matriz jacobiana⁴³⁴³endnote: ⁴³Carl Gustav Jakob Jacobi, 1804 - 1851, matemático alemão. Fonte: Wikipédia: Carl Gustav Jakob Jacobi. da F com

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\jmath_{i,j}(% \boldsymbol{x})=\frac{\partial f_{i}(\boldsymbol{x})}{\partial x_{j}},

(3.2)

onde $F(\boldsymbol{x})=(f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\dotsc,f_{n}(% \boldsymbol{x}))$ e $\boldsymbol{x}=(x_{1},x_{2},\dotsc,x_{n})$ .

3.1.1 Método de Newton

Em revisão

A iteração básica do método de Newton⁴⁴⁴⁴endnote: ⁴⁴Isaac Newton, 1642 - 1727, matemático, físico, astrônomo, teólogo e autor inglês. Fonte: Wikipédia: Isaac Newton. para sistemas de equações consiste em: dada uma aproximação inicial $\boldsymbol{x}^{(0)}\in\mathbb{R}^{n}$ ,

	$\displaystyle\text{resolver}\quad\color[rgb]{0,0,1}\definecolor[named]{% pgfstrokecolor}{rgb}{0,0,1}J_{F}\left(\boldsymbol{x}^{(k)}\right)\boldsymbol{% \delta}^{(k)}=-F\left(\boldsymbol{x}^{(k)}\right)$		(3.3)
	$\displaystyle\text{computar}\quad\color[rgb]{0,0,1}\definecolor[named]{% pgfstrokecolor}{rgb}{0,0,1}\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+% \boldsymbol{\delta}^{(k)}$		(3.4)

para $k=0,1,2,\ldots$ até que um critério de parada seja satisfeito.

Observação 3.1.1.(Convergência)

Para $\boldsymbol{x}^{(0)}$ suficientemente próximo da solução $\boldsymbol{x}^{*}$ , o método de Newton é quadraticamente convergente. Mais precisamente, este resultado de convergência local requer que $J_{F}^{-1}(\boldsymbol{x}^{*})$ seja não singular e que $J_{F}$ seja Lipschitz⁴⁵⁴⁵endnote: ⁴⁵Rudolf Otto Sigismund Lipschitz, 1832 - 1903, matemático alemão. Fonte: Wikipédia. contínua. Consulte [Quarteroni2007a, Seção 7.1] para mais detalhes.

Exemplo 3.1.1.

Consideramos a equação de Burgers⁴⁶⁴⁶endnote: ⁴⁶Jan Burgers, 1895 - 1981, físico neerlandês. Fonte: Wikipédia: Jan Burgers.

\frac{\partial u}{\partial t}+u\frac{\partial u}{\partial x}=\nu\frac{\partial% ^{2}u}{\partial x^{2}}

(3.5)

com $\nu>0$ , condição inicial

u(0,x)=-\operatorname{sen}(\pi x)

(3.6)

e condições de contorno de Dirichlet⁴⁷⁴⁷endnote: ⁴⁷Johann Peter Gustav Lejeune Dirichlet, 1805 - 1859, matemático alemão. Fonte: Wikipédia: Johann Peter Gustav Lejeune Dirichlet. homogêneas

u(t,-1)=u(t,1)=0.

(3.7)

Aplicando o método de Rothe⁴⁸⁴⁸endnote: ⁴⁸Erich Hans Rothe, 1895 - 1988, matemático alemão. Fonte: Wikipédia. com aproximação de Euler⁴⁹⁴⁹endnote: ⁴⁹Leonhard Paul Euler, 1707-1783, matemático e físico suíço. Fonte: Wikipédia: Ronald Fisher. implícita, obtemos

		$\displaystyle\frac{u(t+h_{t},x)-u(t,x)}{h_{t}}+$		(3.8)
		$\displaystyle\quad u(t+h_{t},x)u_{x}(t+h_{t},x)\approx\nu u_{xx}(t+h_{t},x),$		(3.8)

onde $h_{t}>0$ é o passo no tempo. Agora, aplicamos diferenças finitas para obter

		$\displaystyle\frac{u(t+h_{t},x_{i})-u(t,x_{i})}{h_{t}}$		(3.9)
		$\displaystyle\quad+u(t+h_{t},x_{i})\frac{u(t+h_{t},x_{i+1})-u(t+h_{t},x_{i-1})% }{2h_{x}}$
		$\displaystyle\quad\approx\nu\frac{u(t+h_{t},x_{i-1})-2u(t+h_{t},x_{i})+u(t+h_{% t},x_{i+1})}{h_{x}^{2}},$

onde, $x_{i}=(i-1)h_{x}$ , $i=1,\dotsc,n_{x}$ e $h_{x}=1/(n_{x}-1)$ é o tamanho da malha.

Rearranjando os termos e denotando $u^{(k)}_{i}\approx u(t_{k},x_{i})$ , $t_{k}=(k-1)h$ , obtemos o seguinte problema discreto

	$\displaystyle u^{(k+1)}_{1}=0$		(3.10)
	$\displaystyle\frac{1}{h_{t}}u^{(k+1)}_{i}-\frac{1}{h_{t}}u^{(k)}_{i}+\frac{1}{% 2h_{x}}u^{(k+1)}_{i}u^{(k+1)}_{i+1}$
	$\displaystyle\quad-\frac{1}{2h_{x}}u^{(k+1)}_{i}u^{(k+1)}_{i-1}-\frac{\nu}{h_{% x}^{2}}u^{(k+1)}_{i-1}$
	$\displaystyle\quad+2\frac{\nu}{h_{x}^{2}}u^{(k+1)}_{i}-\frac{\nu}{h_{x}^{2}}u^% {(k+1)}_{i+1}=0,$		(3.11)
	$\displaystyle u^{(k+1)}_{n_{x}}=0,$		(3.12)

sendo $u^{(0)}_{i}=-\operatorname{sen}(\pi x_{i})$ , $i=1,\dotsc,n_{x}$ e $k=1,2,\ldots$ .

Este problema pode ser reescrito como segue: para cada $k=0,1,\ldots$ , encontrar $\boldsymbol{w}\in\mathbb{R}^{n_{x}}$ , tal que

F\left(\boldsymbol{w};\boldsymbol{w}^{(0)}\right)=0,

(3.13)

onde $w_{i}=u^{(k+1)}_{i}$ , $w_{i}^{(0)}=u^{(k)}_{i}$ e

	$\displaystyle f_{1}\left(\boldsymbol{w};\boldsymbol{w}^{(0)}\right)=w_{1},$		(3.14)
	$\displaystyle f_{i}\left(\boldsymbol{w};\boldsymbol{w}^{(0)}\right)=\frac{1}{h% _{t}}w_{i}-\frac{1}{h_{t}}w^{(0)}_{i}+\frac{1}{2h_{x}}w_{i}w_{i+1}$
	$\displaystyle\quad-\frac{1}{2h_{x}}w_{i}w_{i-1}-\frac{\nu}{h_{x}^{2}}w_{i-1}+2% \frac{\nu}{h_{x}^{2}}w_{i}-\frac{\nu}{h_{x}^{2}}w_{i+1},$		(3.15)
	$\displaystyle f_{n_{x}}\left(\boldsymbol{w};\boldsymbol{w}^{(0)}\right)=w_{n_{% x}}.$		(3.16)

A matriz jacobiana associada $J=[\jmath_{i,j}]_{i,j}^{n_{x},n_{x}}$ contém

	$\displaystyle\jmath_{i,j}=0,\quad j\neq i-1,i,i+1,$		(3.17)
	$\displaystyle\jmath_{1,1}=1,$		(3.18)
	$\displaystyle\jmath_{1,2}=0,$		(3.19)
	$\displaystyle\jmath_{i,i-1}=\frac{1}{2h_{x}}w_{i}-\frac{\nu}{h_{x}^{2}},$		(3.20)
	$\displaystyle\jmath_{i,i}=\frac{1}{h_{t}}+\frac{1}{2h_{x}}w_{i+1}-\frac{2}{h_{% x}}w_{i-1}+\frac{2\nu}{h_{x}^{2}},$		(3.21)
	$\displaystyle\jmath_{i,i+1}=\frac{1}{2h_{x}}w_{i}-\frac{\nu}{h_{x}^{2}},$		(3.22)
	$\displaystyle\jmath_{n_{x},n_{x}-1}=0$		(3.23)
	$\displaystyle\jmath_{n_{x},n_{x}}=1.$		(3.24)

Implemente este esquema numérico!

Exercícios

Em revisão

E. 3.1.1.

Considere o problema discreto apresentado no Exemplo 3.1.1 para diferentes valores do coeficiente de difusão $\nu=\nu_{0}/\pi$ , $\nu_{0}=1.,0.1,0.01,0.001$ . Simule o problema com cada uma das seguintes estratégias e as compare quanto ao desempenho computacional.

a)

Simule-o aplicando o Método de Newton com o solver linear npla.solve.
b)

Observe que a jacobiana é uma matriz tridiagonal. Simule o problema aplicando o Método de Newton com o solver linear npla.solve_banded.
c)

Aloque a jacobiana como uma matriz esparsa. Então, simule o problema aplicando o Método de Newton com solver linear adequado para matrizes esparsas.

E. 3.1.2.

Desenvolva um esquema upwind para simular a equação de Burgers do Exemplo 3.1.1.

3.1.2 Método Tipo Newton

Em revisão

Existem várias modificações do Método de Newton⁵⁰⁵⁰endnote: ⁵⁰Isaac Newton, 1642 - 1727, matemático, físico, astrônomo, teólogo e autor inglês. Fonte: Wikipédia: Isaac Newton. que buscam reduzir o custo computacional. Há estratégias para simplificar as computações da matriz jacobiana⁵¹⁵¹endnote: ⁵¹Carl Gustav Jakob Jacobi, 1804 - 1851, matemático alemão. Fonte: Wikipédia: Carl Gustav Jakob Jacobi. e para reduzir o custo nas computações das atualizações de Newton.

Atualização Cíclica da Matriz Jacobiana

Em revisão

Geralmente, ao simplificarmos a matriz jacobina $J_{F}$ ou aproximarmos a atualização de Newton $\delta^{(k)}$ , perdemos a convergência quadrática do método (consulte a Observação 3.1.1). A ideia é, então, buscar uma convergência pelo menos super-linear, i.e.

\|e^{(k+1)}\|\approx\rho_{k}\|e^{(k)}\|,

(3.25)

com $\rho_{k}\to 0$ quando $k\to\infty$ . Aqui, $e^{(k)}:=x^{*}-x^{(k)}$ . Se a convergência é superlinear, então podemos usar a seguinte aproximação

\rho_{k}\approx\frac{\|\delta^{(k)}\|}{\|\delta^{(k-1)}\|}

(3.26)

ou, equivalentemente,

\rho_{k}\approx\left(\frac{\|\delta^{(k)}\|}{\|\delta^{(0)}\|}\right)^{\frac{1% }{k}}

(3.27)

Isso mostra que podemos acompanhar a convergência das iterações pelo fator

\beta_{k}=\frac{\|\delta^{(k)}\|}{\|\delta^{(0)}\|}.

(3.28)

Ao garantirmos $0<\beta_{k}<1$ , deveremos ter uma convergência superlinear.

Vamos, então, propor o seguinte método tipo Newton de atualização cíclica da matriz jacobiana.

1.

Escolha $0<\beta<1$
2.

$J:=J_{F}(x^{(0)})$
3.

$J\delta^{(0)}=-F(x^{(0)})$
4.

$x^{(1)}=x^{(0)}+\delta^{(0)}$
5.
Para $k=1,\ldots$ até critério de convergência:
1. (a)
  
  $J\delta^{(k)}=-F(x^{(k)})$
2. (b)
  
  $x^{(k+1)}=x^{(k)}+\delta^{(k)}$
3. (c)
  Se $\|\delta^{(k)}\|/\|\delta^{(0)}\|>\beta$ :
  1. i.
    
    $J:=J_{F}(x^{(k)})$

E. 3.1.3.

Implemente uma versão do método tipo Newton apresentado acima e aplique-o para simular o problema discutido no Exemplo 3.1.1 para $\nu=1.,0.1,0.01,0.001,0.0001$ . Faça uma implementação com suporte para matrizes esparsas.

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados

Política de uso de dados

Matemática Numérica III

3.1 Sistemas Não-Lineares

3.1.1 Método de Newton

Observação 3.1.1.(Convergência)

Exemplo 3.1.1.

Exercícios

E. 3.1.1.

E. 3.1.2.

3.1.2 Método Tipo Newton

Atualização Cíclica da Matriz Jacobiana

E. 3.1.3.

Envie seu comentário