Colabore! Saiba mais screen_rotation

Ao navegar por este site , você concorda com a Política de Uso de Dados.

| | | | |

2 Sistemas Não Lineares e Otimização 2 Sistemas Não Lineares e Otimização 2.2 Problemas de Minimização

2.1 Sistemas Não-Lineares

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

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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}F(\boldsymbol{% x}^{*})=0.

(2.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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}\jmath_{i,j}(% \boldsymbol{x})=\frac{\partial f_{i}(\boldsymbol{x})}{\partial x_{j}},

(2.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})$ .

2.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}\pgfsys@color@rgb@stroke{0}{0}{1}% \pgfsys@color@rgb@fill{0}{0}{1}J_{F}\left(\boldsymbol{x}^{(k)}\right)% \boldsymbol{\delta}^{(k)}=-F\left(\boldsymbol{x}^{(k)}\right)$		(2.3)
	$\displaystyle\text{computar}\quad\color[rgb]{0,0,1}\definecolor[named]{% pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}% \pgfsys@color@rgb@fill{0}{0}{1}\boldsymbol{x}^{(k+1)}=\boldsymbol{x}^{(k)}+% \boldsymbol{\delta}^{(k)}$		(2.4)

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

Observação 2.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 [8, Seção 7.1] para mais detalhes.

Exemplo 2.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}}

(2.5)

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

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

(2.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.

(2.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}}+$		(2.8)
		$\displaystyle\quad u(t+h_{t},x)u_{x}(t+h_{t},x)\approx\nu u_{xx}(t+h_{t},x),$		(2.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}}$		(2.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$		(2.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,$		(2.11)
	$\displaystyle u^{(k+1)}_{n_{x}}=0,$		(2.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,

(2.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},$		(2.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},$		(2.15)
	$\displaystyle f_{n_{x}}\left(\boldsymbol{w};\boldsymbol{w}^{(0)}\right)=w_{n_{% x}}.$		(2.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,$		(2.17)
	$\displaystyle\jmath_{1,1}=1,$		(2.18)
	$\displaystyle\jmath_{1,2}=0,$		(2.19)
	$\displaystyle\jmath_{i,i-1}=\frac{1}{2h_{x}}w_{i}-\frac{\nu}{h_{x}^{2}},$		(2.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}},$		(2.21)
	$\displaystyle\jmath_{i,i+1}=\frac{1}{2h_{x}}w_{i}-\frac{\nu}{h_{x}^{2}},$		(2.22)
	$\displaystyle\jmath_{n_{x},n_{x}-1}=0$		(2.23)
	$\displaystyle\jmath_{n_{x},n_{x}}=1.$		(2.24)

Implemente este esquema numérico!

Exercícios

Em revisão

E. 2.1.1.

Considere o problema discreto apresentado no Exemplo 2.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. 2.1.2.

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

2.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 2.1.1). A ideia é, então, buscar uma convergência pelo menos super-linear, i.e.

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

(2.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)}\|}

(2.26)

ou, equivalentemente,

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

(2.27)

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

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

(2.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. 2.1.3.

Implemente uma versão do método tipo Newton apresentado acima e aplique-o para simular o problema discutido no Exemplo 2.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

As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a Política de Uso de Dados para mais informações. Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

| | | |