Sejam A e B dois conjuntos. O produto cartesiano de A por B é dado por AxB = {(a, b) | a ∈ A, b ∈ B}, isto é, o conjunto de todos os possíveis pares ordenados cujo primeiro elemento pertence a A e o segundo pertence a B. Se A tem n elementos e B tem m elementos, o produto cartesiano terá nm elementos distintos. Observe que se A ≠ B então AxB ≠ BxA.
Dizemos que R é uma relação de A em B se R ⊆ AxB, isto é, se R é um subconjunto do produto cartesiano de A por B. Desta forma, existem 2^{nm} possíveis relações de A em B. Se (a,b) ∈ R, dizemos que a se relaciona com b.
Uma relação f é uma função de A em B (e escrevemos f: A -> B) se os dois critérios abaixo forem atendidos:
- todo elemento a de A se relaciona com algum elemento b de B;
- cada elemento a de A está relacionado com um único elemento b de B.
Uma função f é dita injetora se f(a) = f(b) implica em a = b (isto é, cada elemento do conjunto B está relacionado com um único elemento do conjunto A); f é dita sobrejetora se, para qualquer elemento b ∈ B, existe um elemento a ∈ A tal que f(a) = b. Uma função que é, ao mesmo tempo, injetora e sobrejetora é dita bijetora.
Veja que a classificação anterior está relacionada diretamente aos dois critérios da definição de funções. Seja R a relação de B em A definida por R = {(b, a) | b ∈ B, a ∈ A, e f(a) = b}. Se a relação R atender ao primeiro critério, então a função f é sobrejetora; se atender o segundo, f é injetora. Se a relação R atende a ambos critérios, efetivamente R é uma função, denominada função inversa de f.
Assim, uma função é inversível se for bijetora, e esta função estabelece uma relação um-a-um entre os elementos de A e B. Se A e B forem conjuntos finitos, então ambos terão o mesmo número de elementos.
Na notação y = f(x), x é a variável independente e y é a variável dependente: dizemos que y é função de x, ou que y depende de x. Isto significa que, conhecido o valor de x, é possível determinar o valor de y. Uma variável pode ser dependente de mais de uma variável: por exemplo, área A de um retângulo depende dos valores das medidas da base b e da altura h do retângulo, ou seja, A = A(b, h).
Seja f: A -> B, onde 0 (zero) pertence a B. Dizemos que x ∈ A é um zero de f se f(x) = 0. Uma função pode não ter, ter finitos ou infinitos zeros. Por exemplo, a função f(x) = 1/x não tem zeros nos reais; o Teorema Fundamental da Álgebra diz que todo polinômio de grau n tem n raízes complexas; e a função f(x) = sen(x) tem infinitos zeros: qualquer múltiplo de 2𝜋.
Se f é uma função contínua em um intervalo I dos reais (isto é, para qualquer elemento a ∈ I, o limite de f(x) quanto x tende a a existe e é igual a f(a)) tal que, para dois valores a, b ∈ I, f(a)f(b) < 0 (isto é, f(a) e f(b) tem sinais opostos), então existe um valor c ∈ (a,b) tal que f(c) = 0. O valor de c pode ser aproximado por busca binária, conforme mostra o código abaixo. Tal método é conhecido como método da bisseção.
// Assuma que a função f(double) esteja definida, a < b e que f(a)*f(b) < 0
// eps é o erro esperado
double root(double a, double b, double eps)
{
while (fabs(a - b) > eps)
{
double c = (a + b)/2;
y = f(c);
// c é uma boa aproximação para o zero
if (fabs(y) < eps)
return c;
// Determina em qual dos intervalos ( (a,c) ou (c,b) ) está o zero
if (f(a)*y < 0)
b = c;
else
a = c;
}
return (a + b)/2;
}Por conta de possíveis erros de precisão, este algoritmo pode não convergir ou não melhorar sua precisão após N passos. Implementações alternativas usam um número de passos N pré-determinado como critério de parada.
// Assuma que a função f(double) esteja definida, a < b e que f(a)*f(b) < 0
// N é o número de iterações do algoritmo
double root(double a, double b, int N)
{
while (N--)
{
double c = (a + b)/2;
y = f(c);
// Determina em qual dos intervalos ( (a,c) ou (c,b) ) está o zero
if (f(a)*y < 0)
b = c;
else
a = c;
}
return (a + b)/2;
}- Codeforces
- UVA
WIKIPEDIA. Bissection Method. Acesso em 15 de agosto de 2017.