Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como posso implementar uma classe para encontrar numericamente o máximo e mínimo de funções?

0 votos
17 visitas
perguntada Ago 12 em Programação Computacional por Gustavo Libório (1 ponto)  

Esta pergunta corresponde ao exercício 7.34 do livro "A Primer on Scientific Programming with Python", quinta edição; de Langtangen.

Compartilhe

1 Resposta

0 votos
respondida Ago 12 por Gustavo Libório (1 ponto)  
editado Ago 13 por Gustavo Libório

O exercício propõe criar uma classe para modelar a seguinte situação: temos uma função real definida em um intervalo e queremos encontrar máximos e mínimos locais e globais. Para tanto, vamos selecionar um número (grande, quanto maior melhor) de pontos nesse intervalo e averiguar se eles são extremos com relação aos vizinhos, ou seja, se são máximos ou mínimos locais. Feito isso, basta selecionar o maior e o menor e esses serão os extremos globais.

Faremos esse procedimento criando uma classe chamada MinMax. O código pode ser exemplificado por:

class MinMax:

    def __init__(self, f, a, b, n):
        """
         f: função
        a: início do domínio nos reais
        b: fim do domínio nos reais
        n: quantos pontos do domínios devem ser avaliados
        """
        self.f = f
        self.a = a
        self.b = b
        self.n = n
        self._find_extrema()

    def __str__(self):
        ...

    def _find_extrema(self):
        maximos = []
        minimos = []
        grid = [self.a + i * (self.b - self.a) / self.n for i in range(1, self.n + 1)]
        grid = [self.a] + grid
        for i, value in enumerate(grid):
            if 0 < i < len(grid) - 1:
                if self.f(value) >= self.f(grid[i - 1]) and self.f(value) >= self.f(grid[i + 1]):
                    maximos.append(value)
                if self.f(value) <= self.f(grid[i - 1]) and self.f(value) <= self.f(grid[i + 1]):
                    minimos.append(value)
            elif i == 0:
                if self.f(value) >= self.f(grid[i + 1]):
                    maximos.append(value)
                if self.f(value) <= self.f(grid[i + 1]):
                    minimos.append(value)
            else:
                if self.f(value) >= self.f(grid[i - 1]):
                    maximos.append(value)
                if self.f(value) <= self.f(grid[i - 1]):
                    minimos.append(value)
        f_max = max(list(map(self.f, maximos)))
        f_min = min(list(map(self.f, minimos)))
        self.grid = grid
        self.maximos_locais = maximos
        self.minimos_locais = minimos
        self.maximos_globais = [i for i in maximos if self.f(i) >= f_max]
        self.minimos_globais = [i for i in minimos if self.f(i) <= f_min]

A classe criada acima define, em seu método especial __init__, todo o procedimento de otimização numérica. De início, ao instanciarmos a classe, são registrados como atributos as informações relevantes de input, no caso: a função a ser otimizada, os limites do intervalo \([a,b]\) que é o domínio e o número de pontos do grid onde calcularemos os valores da função.

Subsequentemente a essas definições, o processo de inicialização chama outrao método da classe, _find_extrema. O processo que esse método implementa é simples e objetivo: calcula o valor da função em todos pontos do grid e salva aqueles que são extremos locais, incluindo os extremos do intervalo. Após isso, a instrução é obter os extremos globais a partir dos locais, ou seja, escolher dos extremos locais aqueles que tê imagem mais extrema. Esses valores são então salvos como atributos da classe.

Para tornar mais acessível são adicionados métodos para obter os extremos e também o método especial __str__ para tornar o objetivo chamável, como visto abaixo:

def __str__(self):
    print("Extremos da função")
    print("------------------")
    print("Máxmimos globais: ", self.maximos_globais)
    print("Mínimos globais:", self.minimos_globais)
    print("Máxmimos locais:", self.maximos_locais)
    print("Mínmimos locais:", self.minimos_locais)
    return "------------------"

def get_global_maxima(self):
        return [[i, self.f(i)] for i in self.maximos_globais]

    def get_global_minima(self):
        return [[i, self.f(i)] for i in self.minimos_globais]

    def get_local_maxima(self):
        return [[i, self.f(i)] for i in self.maximos_locais]

    def get_local_minima(self):
        return [[i, self.f(i)] for i in self.minimos_locais]

Essa classe já está pronta para o uso. Para completar o exercício, contudo, pede-se ainda que se implemente um refino de extremos usando a derivada numérica e o algoritmo de bisection. Para tanto, o procedimento será criar uma método que, ao ser chamado, refina cada extremo encontrado da seguinte maneira: pega o ponto interno do grid que é extremo, \(x_i\) por exemplo. Sabe-se que, se houver mínimo local no intervalo; então devemos ter que \(f'(x_{i-1}\) e \(f'(x_{i+1}\) tem sinais diferentes e \(f'(x^*)=0\) em algum ponto. Então se aplica o algoritmo de dividir sucessivamente o intervalo onde se sabe que \(x^*\) se encontra para refinar o ponto de ótimo encontrado. Em código podemos fazer assim:

def _refine_extrema(self, n_refinos):

    a, b, grid = self.a, self.b, self.grid
    maximos_refinados = []
    minimos_refinados = []
    df = Derivative(self.f)
    for i in self.maximos_globais:
        new_max = i
        index_0 = self.grid.index(i)
        if i != a and i != b:
            q = grid[index_0-1]
            Q = grid[index_0+1]
            for _ in range(0, n_refinos):
                new_max = (q+Q)/2
                if abs(df(new_max)) <= 1E-6:
                    break
                elif df(new_max) > 0:
                    q = new_max
                elif df(new_max) < 0:
                    Q = new_max
            maximos_refinados.append(new_max)

    for i in self.minimos_globais:
        new_min = i
        index_0 = self.grid.index(i)
        if i != a and i != b:
            q = grid[index_0 - 1]
            Q = grid[index_0 + 1]
            for _ in range(0, n_refinos):
                new_min = (q + Q) / 2
                if abs(df(new_min)) <= 1E-5:
                    break
                elif df(new_min) > 0:
                    Q = new_min
                elif df(new_min) < 0:
                    q = new_min
            minimos_refinados.append(new_min)
    return {"minimos": minimos_refinados, "maximos": maximos_refinados}

Agora podemos aplicar nossa classe a uma função qualquer! Vamos testar com \(f(x)=x^2\) no intervalo \([-1,2]\), com 100 pontos no grid:

if __name__ == "__main__":
    f = lambda x: (x)**2
    m = MinMax(f, -1, 2, 100)
    m_r = m._refine_extrema()
    print(m)
    print(m_r)

##Output:
"""
Extremos da função
------------------
Máxmimos globais:  [2.0]
Mínimos globais: [-0.010000000000000009]
Máxmimos locais: [-1, 2.0]
Mínmimos locais: [-0.010000000000000009]
------------------
Extremos refinados
{'minimos': [-0.0006250000000000006], 'maximos': []}
"""
...