Prévia do material em texto
M
A
RIN
A
V
A
RG
A
S
MARINA VARGAS
M
A
TEM
Á
TICA
PA
RA
CO
M
PUTA
ÇÃ
O
M A T E M Á T I C A
COMPUTAÇÃO
PARA
Código Logístico
I000122
ISBN 978-65-5821-071-9
9 7 8 6 5 5 8 2 1 0 7 1 9
M
A
RIN
A
V
A
RG
A
S
MARINA VARGAS
M
A
TEM
Á
TICA
PA
RA
CO
M
PUTA
ÇÃ
O
M A T E M Á T I C A
COMPUTAÇÃO
PARA
Código Logístico
I000122
ISBN 978-65-5821-071-9
9 7 8 6 5 5 8 2 1 0 7 1 9
Matemática para
Computação
Marina Vargas
IESDE BRASIL
2021
© 2021 – IESDE BRASIL S/A.
É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito da autora e do
detentor dos direitos autorais.
Projeto de capa: IESDE BRASIL S/A. Imagem da capa: whiteMocca/majcot/Lantica/Shutterstock
Todos os direitos reservados.
IESDE BRASIL S/A.
Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200
Batel – Curitiba – PR
0800 708 88 88 – www.iesde.com.br
CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO
SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ
V427m
Vargas, Marina
Matemática para computação / Marina Vargas. - 1. ed. - Curitiba [PR]
: Iesde, 2021.
160 p. : il.
Inclui bibliografia
ISBN 978-65-5821-071-9
1. Computação - Matemática. 2. Programação (Computadores). 3.
Algoritmos. 4. Matrizes (Matemática). I. Título.
21-72772
21-72772 CDD: 518.1
CDU: 519.165:004.021
Marina Vargas Pós-doutora em Mecânica Computacional pela
Universidade Federal do Paraná (UFPR). Doutora
e mestre em Métodos Numéricos em Engenharia
pela UFPR. Especialista em Educação Matemática
e licenciada em Matemática pela Universidade
Paranaense (Unipar). Professora no ensino superior
nas modalidades presencial e a distância, ministra
as disciplinas Cálculo de Funções de uma e mais
Variáveis, Álgebra Linear, Geometria Analítica, Métodos
Numéricos, Teoria dos Números, Pesquisa Operacional,
Matemática Aplicada, Estatística Aplicada e Métodos
Quantitativos. Atua também como professora
conteudista em diversas instituições e empresas.
Atualmente, desenvolve pesquisas nas áreas de
programação matemática, mecânica computacional,
educação matemática e educação em engenharias.
SUMÁRIO
Agora é possível acessar os vídeos do livro por
meio de QR codes (códigos de barras) presentes
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando
a câmera fotográ�ca de seu smartphone ou tablet
para o QR code.
Em alguns dispositivos é necessário ter instalado
um leitor de QR code, que pode ser adquirido
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
SUMÁRIO
Agora é possível acessar os vídeos do livro por
meio de QR codes (códigos de barras) presentes
no início de cada seção de capítulo.
Acesse os vídeos automaticamente, direcionando
a câmera fotográ�ca de seu smartphone ou tablet
para o QR code.
Em alguns dispositivos é necessário ter instalado
um leitor de QR code, que pode ser adquirido
gratuitamente em lojas de aplicativos.
Vídeos
em QR code!
1 Por que estudar matemática? 9
1.1 O que é matemática computacional 9
1.2 Idealização de um algoritmo numérico 15
1.3 Relações de recorrência 19
1.4 Conceito de função no aspecto computacional 22
1.5 Diferenças entre problemas qualitativos e quantitativos 24
2 Noções sobre sistemas de numeração 29
2.1 Sistemas de numeração 29
2.2 Representação numérica 35
2.3 Representação em ponto flutuante 43
2.4 Erros numéricos 46
3 Matrizes 54
3.1 Vetores de uma matriz 55
3.2 Análise do algoritmo padrão para multiplicação de matrizes 58
3.3 Bases 61
3.4 Fatoração matricial – Método de Gauss 64
3.5 Decomposição LU e LDU 69
3.6 Inversa de uma matriz 75
4 Sistemas de equações lineares 81
4.1 Sistemas equivalentes e operações 82
4.2 Sistemas triangulares e escalonados 86
4.3 Eliminação gaussiana 94
4.4 Condicionamento de sistemas lineares 101
4.5 Métodos iterativos 108
5 Grafos e árvores 123
5.1 O que é um grafo: terminologia e tipos 124
5.2 Representação computacional de um grafo 132
5.3 Conceito de árvore 138
5.4 Raízes e árvores binárias 142
5.5 Introdução a procedimentos de busca 145
Resolução das atividades 150
Nesta obra, buscamos trazer os conceitos básicos da
matemática para o trabalho, não só com algoritmos a serem
implementados nas mais diversas linguagens de programação,
mas, principalmente, a lógica por trás dos cálculos computacionais.
Quando mencionamos cálculos computacionais, além de
pensarmos a forma como a máquina opera e, portanto, trabalha
com sistemas de numeração, erros numéricos e vetores, é
necessário falarmos de conceitos, como sistemas em rede e grafos,
pois estes estão diretamente relacionados às teorias mais atuais
da computação, como inteligência artificial, redes neurais etc.
Desse modo, destinamos o primeiro capítulo a apresentar
um pouco da história do desenvolvimento da computação, que
está diretamente ligada ao desenvolvimento da matemática.
Apresentamos alguns dos nomes importantes dessa história e
mostramos suas contribuições para a matemática computacional.
Além disso, contextualizamos conceitos como algoritmo e
relações de recorrência e tratamos da diferença entre problemas
qualitativos e quantitativos.
No segundo capítulo, discorremos sobre os sistemas de
numeração aditivos e posicionais, destacando o sistema de
numeração posicional decimal, relacionando-o com o sistema
por trás das máquinas eletrônicas: o sistema posicional binário.
Também trabalhamos o conceito de erro entre o resultado
esperado e o resultado encontrado. Para esse fim, construímos
um fluxograma que mostra, com base em um modelo real,
as ramificações possíveis até que seja obtida a solução
numérica/computacional desejada.
A proposta do Capítulo 3 é a explanação sobre os conceitos
de vetores e matrizes e as operações que os representam. Essa
escolha se dá pela facilidade em operar computacionalmente por
meio dessas estruturas matemáticas. Assim, seu entendimento
é essencial para a matemática computacional. Além disso,
trabalhamos com a decomposição de matrizes, preparando
caminho para o tema do próximo capítulo.
APRESENTAÇÃOVídeo
8 Matemática para Computação
Nesse contexto, entramos no quarto capítulo, que trata dos sistemas
de equações e visa trazer técnicas numéricas e algoritmos que permitam a
implementação computacional desses sistemas. Podemos exemplificar essa
necessidade por meio de uma extensa lista de aplicações, entre elas: redes de
computadores, resolução de modelos que representam fenômenos físicos e
gerenciamento de sistemas. No entanto, além desse contexto, elas podem ser
diretamente aplicadas ao próximo capítulo, que aborda os grafos.
O Capítulo 5 apresenta a concepção de grafo. Por intermédio de um
grafo, podemos representar problemas aplicados e identificar situações em
que a busca por um caminho mínimo não só agiliza processos, mas também
minimiza custos. Para essa construção, retomamos o uso de matrizes e
vetores, sendo essa uma importante forma de implementação desse conceito.
É fácil notarmos que os três últimos capítulos têm uma conexão importante
dentro da matemática computacional e se comunicam com a computação de
maneira quase que natural. Esse é um dos fatores para que esses conceitos
estejam em todos os melhores cursos de computação e tecnologia da
informação com todas as suas ramificações.
Este é o foco desta obra. Nossa proposta é trazer o raciocínio lógico
matemático por trás da necessidade de implementação computacional de
problemas aplicados na área da tecnologia da informação e computação.
Esperamos que este livro auxilie no aprendizado para a formação de um
melhor profissional na área escolhida.
Bons estudos!
Por que estudar matemática? 9
1
Por que estudar
matemática?
A matemática está por trás da lógica de programação de uma maneira
que você talvez nunca tenha parado para pensar. A ciência da programa-
ção começou por intermédio de matemáticos curiosos e muito à frente de
seus tempos, que tentavam otimizarprocessos e avançar com a possibi-
lidade dos cálculos serem realizados por máquinas. A ideia era que essas
máquinas recebessem mais do que números, ou seja, que pudessem re-
ceber instruções. E eles conseguiram!
Neste capítulo, destinado ao estudo da ligação da matemática com a
computação, vamos conhecer um pouco da história desses matemáticos
e compreender por que é tão importante conhecer matemática para dis-
cutirmos sobre computação.
Com o estudo deste capítulo, você será capaz de:
• compreender a matemática por trás de conceitos
computacionais;
• reconhecer a diferença entre matemática teórica e matemá-
tica computacional;
• identificar o uso de cálculos numéricos por trás de algoritmos;
• relacionar o conceito de função em diferentes realidades
computacionais;
• compreender as dimensões quantitativas de um problema.
Objetivos de aprendizagem
1.1 O que é matemática computacional
Vídeo
Quando pensamos em matemática computacional, precisamos en-
tender, em primeiro lugar, como um “computador” faz cálculos. Aqui,
estamos chamando de “computador” todos os objetos que são capazes
de realizar cálculos discretos, como: calculadoras, computadores, celu-
10 Matemática para Computação
lares, dentre outros. Assim, todos os objetos que utilizam o princípio de
abertura e fechamento de chaves e que permitem ou não a passagem
de energia serão analisados perante a mesma lógica de construção
para obtenção da chamada matemática computacional.
Quando escrevemos os cálculos, percebemos que eles serão reali-
zados usando um princípio mecânico básico de abertura e fechamento
de chaves, e que estamos envolvendo nesse processo uma lógica bi-
nária. Essa lógica precisa ser processada e interpretada. É nesse ponto
que entram os diferentes hardwares de processamento e, em conjun-
to, os softwares que interpretam esses dados processados.
É justamente por esse desenvolvimento que começamos a identifi-
car a existência de erros numéricos, os quais podem surgir no processo
de cálculo. Além disso, é por meio da lógica binária que identificamos o
teor discreto da matemática computacional.
Agora vamos conhecer alguns dos nomes que permitiram que a ma-
temática computacional acontecesse.
1.1.1 Ada Lovelace
Augusta Ada Byron King, Condessa de Lovelace, nasceu em 10 de
dezembro de 1815 na cidade de Londres e faleceu em 27 de
novembro de 1852, aos 36 anos, no bairro Marylebone, na
mesma cidade em que nasceu, na Inglaterra. Ada Lovela-
ce é conhecida como a primeira programadora da
história.
Ela viveu em uma época em que as mulheres não
eram bem-vistas em universidades. Por esse motivo, e com
estímulo de sua mãe (Anne Isabella “Anabella” Byron, Baro-
nesa de Wentworth), Ada estudou em casa com tutores como
Augustus De Morgan e Mary Sommerville, que se tornou não apenas
sua tutora, mas sua amiga (BIM, 2018).
Foi Sommerville quem apresentou Ada ao cientista Charles Babba-
ge (1791-1871), matemático, conhecido por ter criado a primeira má-
quina capaz de resolver e imprimir cálculos matemáticos.
A invenção, chamada de máquina analítica (Figura 1), é considera-
da precursora dos computadores modernos (BROMLEY, 1982).
Ada Lovelace
Ke
lso
n/W
ikim
edia
Comm
ons
Por que estudar matemática? 11
Charles Babbage
Connormah/Wikimedia Commons
Figura 1
Réplica da máquina analítica
Br
un
o
Ba
rra
l/W
ik
im
ed
ia
C
om
m
on
s
Mas foi Lovelace quem criou o primeiro algoritmo resolvido pela
máquina analítica, publicado como nota de rodapé de um artigo de
Babbage. Nesse material, Ada descreveu a possibilidade de a máqui-
na realizar cálculos complexos envolvendo letras, números e sím-
bolos, além de instruções que permitiam repetição (looping). Além
disso, constava nessas notas um algoritmo que permitia o cálculo
para os números de Bernoulli.
Foi por causa desse artigo que Babbage percebeu a geniali-
dade da moça e aceitou trabalhar em conjunto com ela, o que
se transformou em uma grande amizade.
Na matéria “Ada Lovelace desafiou o machismo e se tornou
a primeira programadora da história”, que retrata a história de
Ada Lovelace sob o olhar da escritora Angela Saini, Simões (2021)
relata que a “matemática estava muito à frente de seu tempo quan-
do teve a genial ideia do que um algoritmo seria capaz de fazer”.
Ada e Babbage trabalharam juntos ao longo de muitos anos. Nesse
período, ela desenvolveu diversos algoritmos que permitiriam que a má-
quina analítica computasse valores de funções matemáticas. Esses algo-
ritmos foram posteriormente analisados por um outro matemático – que
será apresentado mais à frente.
Para conhecer um pouco
mais da história e feitos
de Babbage e Lovelace,
sugerimos dois vídeos.
O primeiro conta a vida
de Lovelace. Já o segundo,
traz a parceria entre
Lovelace e Babbage na
idealização e construção
da máquina analítica.
• Biografias 23 – Ada Lovelace, a
primeira programadora.
Disponível em: https://www.
youtube.com/
watch?v=gcNKhlKW7uQ&ab_
channel=OMundoDaCi%C3
%AAncia. Acesso em: 31 maio 2021.
• O primeiro Computador do
Mundo – Charles Babbage & Ada
Lovelace – Documentário.
Disponível em: https://
www.youtube.com/
watch?v=35MwtZ5MKjM.
Acesso em: 31 maio 2021.
Vídeo
https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia
https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia
https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia
https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia
https://www.youtube.com/watch?v=gcNKhlKW7uQ&ab_channel=OMundoDaCi%C3%AAncia
https://www.youtube.com/watch?v=35MwtZ5MKjM
https://www.youtube.com/watch?v=35MwtZ5MKjM
https://www.youtube.com/watch?v=35MwtZ5MKjM
12 Matemática para Computação
Mas o que é um algoritmo?
Fazendo uma analogia simples, um algoritmo é como uma receita
de bolo que mostra detalhadamente os métodos necessários para re-
solver uma atividade.
Na matemática, um algoritmo é fundamental para que consigamos
resolver uma expressão. A seguir, veremos que na computação tam-
bém é essencial.
Exemρlo 1
Pense em um cálculo qualquer. Pode ser um cálculo simples, como
(2 + 2) + 2
Um algoritmo para esse cálculo pode ser montado como a seguir:
Início:
Resolva primeiro os parênteses.
Laço:
Dentro dos parênteses procure operações de multiplicação e
divisão.
Se não houver, resolva as operações de adição e subtração.
Com o resultado da soma, elimine os parênteses e some esse nú-
mero com o restante das parcelas.
Fim.
O Exemplo 1 traz um algoritmo muito simples, escrito de maneira
direta e, no momento, sem pensarmos como essa lista de regras seria
realmente programada para que a máquina pudesse resolver. Porém,
com esse exemplo, conseguimos visualizar a necessidade de regras
claras sobre a maneira de resolução, pois sem elas o computador não
irá operar corretamente. Essa forma de escrita que adotamos para re-
presentar um algoritmo é conhecida como pseudocódigo ou portugol.
Fica claro que sem os algoritmos e esse avanço trazido por Ada
Lovelace é quase impossível pensarmos na ciência da computação e na
matemática avançada da maneira que a vemos hoje.
Por que estudar matemática? 13
1.1.2 Alan Turing
Alan Mathison Turing nasceu em 23 de junho de 1912,
na cidade de Paddington, na Inglaterra, e faleceu em
7 de junho de 1954, aos 41 anos, em Wilmslow,
Inglaterra. Alan Turing é conhecido como o pai da
ciência da computação e da inteligência artificial.
Estudou na Universidade de Cambridge, onde
obteve seu bacharelado em matemática e concluiu
seu mestrado. Prosseguiu seus estudos, obtendo
seu doutorado em matemática pela universidade de
Princeton.
Dentre os vários projetos que fizeram desse matemático o “cien-
tista do século 20”, em pesquisa 1 realizada pela BBC no ano de 2019,
ficando à frente de Albert Einstein e Marie Curie, está a chamada má-
quina de Turing, também conhecido como máquina universal.
A máquina de Turing é um modelo abstrato que permite mani-
pular símbolosem uma fita de acordo com regras preestabelecidas,
restringindo-se apenas aos aspectos lógicos do seu funcionamento,
como a memória, os estados e as transições. Por meio dessa máqui-
na, podemos modelar qualquer computador digital.
Turing foi um dos responsáveis para que os Aliados – incluindo
a Inglaterra – ganhassem uma importante vantagem em relação à
Alemanha na Segunda Guerra Mundial. Sua máquina física Bombe,
construída com os conceitos da máquina universal e tendo como
referência os trabalhos de Lovelace e Babbage, dentre outros, per-
mitiu que os Aliados quebrassem o código alemão Enigma em Blet-
chley Park. Dessa forma, eles passaram a ter conhecimento das
estratégias que seriam usadas e puderam se antecipar aos ataques,
levando à vitória.
Muitos outros nomes estão envolvidos na construção histórica
da computação e na forma como trabalhamos com a matemática
hoje. Dentre eles, citamos John Von Neumann (1903-1957) e Norbert
Wiener (1894-1964).
Contudo, percebemos que Ada Lovelace e Alan Turing, dois ma-
temáticos, viram a matemática muito além do que cálculos reali-
zados à mão, com abordagem abstrata e sem aplicação no mundo
Alan Turing
Bruno Barral/Wikimedia Commons
Acesse na íntegra a pes-
quisa Scientists of the 20th
Century. Disponível em:
https://www.bbc.co.uk/
programmes/p06y1tmk.
Acesso em: 30 ago. 2021
1
Para saber um pouco
mais sobre a vida e con-
tribuição de Turing, suge-
rimos a matéria 17 fatos
e curiosidades sobre a vida
do Alan Turing, publicada
pela revista Galileu.
Disponível em: https://revistagalileu.
globo.com/Cultura/noticia/2018/06/
17-fatos-e-curiosidades-sobre-vi-
da-do-alan-turing.html. Acesso em:
31 maio 2021.
Leitura
O filme O jogo da imitação,
de 2014 – indicado ao
Oscar em duas categorias
–, retrata vida e morte de
Alan Turing, o processo de
criação da máquina física
Bombe e a guerra.
Direção: Morten Tyldum. Reino
Unido: Warner Bros, 2014.
Filme
https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html
https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html
https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html
https://revistagalileu.globo.com/Cultura/noticia/2018/06/17-fatos-e-curiosidades-sobre-vida-do-alan-turing.html
14 Matemática para Computação
físico. Por meio de seus raciocínios analíticos, viram a possibilidade
de resolver problemas de maneira mais rápida e otimizada e con-
seguiram colocar em prática o que hoje chamamos de matemática
computacional.
1.1.3 Por que estudar matemática
computacional?
A matemática computacional permite que trabalhemos com pro-
blemas extremante complexos que não poderiam ser resolvidos por
uma única pessoa e, muitas vezes, nem mesmo por uma grande
equipe.
Esse conceito pode parecer absurdo, mas é a realidade de nossos
dias. Os computadores mudaram a vida em sociedade e por meio
deles conseguimos trabalhar com operações complexas, com modelos
cada vez mais elaborados que representam o mundo real, e analisar
uma infinidade de dados que não conseguiríamos avaliar em gera-
ções passadas.
Além disso, entenda, sem uma quantidade de dados razoavel-
mente grande – em torno de milhões – não teríamos os serviços
cada vez mais personalizados, os sistemas otimizados e a precisão
em diversos processos, que são exigências do mundo atual.
Dessa forma, podemos entender a matemática computacional
como uma nova ciência que une os conceitos da computação e da
matemática e nos permite resolver problemas, por exemplo, repre-
sentar o genoma humano, calcular a eficiência e ajuste de foguetes,
dentre outros, que não seriam possíveis sem os computadores.
Contudo, para que possamos levar para o computador a mate-
mática por traz desses avanços, inicialmente precisamos compreen-
der alguns conceitos, como: o que são dados quantitativos, como
montar uma relação de recorrência ou, ainda, como escrever um
algoritmo que resolva problemas envolvendo vetores, matrizes, sis-
temas de equações, funções, dentre muitos outros.
É desses questionamentos que nasce a ciência matemática com-
putacional. Desse modo, precisamos entender a matemática e como
Por que estudar matemática? 15
a máquina processa essa matemática? Com certeza! Além disso, pre-
cisamos representar os problemas cotidianos em modelos matemá-
ticos para que tenhamos essa associação.
Desse modo, vamos trazer um pouco mais da matemática que
precisamos compreender para que seja possível criar as oportunida-
des de aplicação usando os computadores.
Ev
er
et
t C
ol
le
ct
io
n/
Sh
ut
te
rs
to
ck
Figura 2
Mecanismo de Gottfried Leibniz
1.2 Idealização de um algoritmo numérico
Vídeo
Em 1671, o filósofo e mate-
mático Gottfried Wilhelm Leibniz,
um dos criadores – juntamente
com Isaac Newton – do cálculo
diferencial e integral, construiu
um mecanismo (Figura 2) que
permitia realizar multiplica-
ções e divisões mediante adi-
ções e subtrações sucessivas.
Na época, a metodologia usada
por Leibniz ocasionava muitos
erros, sendo descartado seu
uso. Entretanto, manteve-se a
ideia principal, que permitia,
por meio de operações simples,
escrever outras operações.
A primeira calculadora capaz
de efetuar as quatro operações
aritméticas básicas foi construí-
da pelo francês Charles Xavier Thomas em 1820. Considerada a primei-
ra calculadora possível de ser comercializada, a máquina de Thomas
executava as multiplicações por meio de somas, como idealizado por
Leibniz, e as divisões podiam ser executadas com auxílio do usuário.
Contudo, nenhuma dessas máquinas era programável, ou seja, era
possível entrar com valores numéricos, mas não era possível passar
instruções.
16 Matemática para Computação
Vimos que um algoritmo é constituído exatamente de ins-
truções a serem realizadas e esse feito começa a ser possível
apenas com a criação da máquina de Lovelace e Babbage
e, posteriormente, com a máquina de Turing.
Um algoritmo é uma etapa essencial para que uma
construção matemática possa ser executada por um
computador. Ao construirmos um algoritmo, não preci-
samos pensar qual será a linguagem de programação utili-
zada, mas sim como queremos que o cálculo seja realizado.
Exemρlo 2
Acompanhe o algoritmo a seguir e observe o resultado obtido.
Variáveis inteiras: a, soma
Seja a=0 e Soma=0
Se Soma<6, faça:
a=a+1
Soma=Soma+a
Imprima Soma
Vamos interpretar esse algoritmo:
Variáveis inteiras: a, soma #Declaração de variáveis. Nesse pon-
to apresentamos a que conjunto elas pertencem.
Seja a=0 e Soma=0 #Valores iniciais das variáveis.
Se Soma<6, faça: #Note que, nesse ponto temos um laço ou looping
que será executado enquanto a condição “Soma<6” for válida.
a=a+2 #Cada vez que entramos no laço, precisamos pegar
o último valor de a e acrescentar 1, gerando um novo valor
de a.
Soma=Soma+a #Cada vez que entramos no laço,
precisamos pegar o último valor de Soma e acrescentar a,
gerando um novo valor para Soma.
Imprima Soma #Quando não for mais possível realizar o laço, ou
seja, quando “Soma ≥ 6”, imprime-se o último valor encontrado
para a variável Soma.
Charles Xavier Thomas
Ba
sti
en
M/
Wi
kim
edi
a Co
mmo
ns
Por que estudar matemática? 17
Quadro 1
Resumo do algoritmo
a Soma
Início 0 0
Laço a=0+1=1 Soma=0+1=1
Laço a=1+1=2 Soma=1+2=3
Laço a=2+1=3 Soma=3+3=6
Imprime Soma=6
Fonte: Elaborado pela autora.
De acordo com Campos Filho (2007, p. 1),
o cálculo numérico é uma metodologia para resolver problemas
matemáticos por intermédio de um computador, sendo ampla-
mente utilizado por engenheiros e cientistas. Uma solução via
Cálculo numérico é sempre numérica, enquanto os métodos
analíticos usualmente fornecem um resultado em termos de
funções matemáticas.
Para a construção de um algoritmo numérico, são necessárias as
quatro operações aritméticas fundamentais e as operações lógicas
que são: comparação, conjunção,disjunção e negação. A vantagem
é que essas operações são exatamente as operações realizadas pelo
processador de um computador.
O processo se dá inicialmente pelo fechamento e abertura de cha-
ves que permitem a passagem ou não de energia. Esse mecanismo é
compilado em zeros e uns. Isto é, quando a energia passa, o compila-
dor entende esse resultado como 1 (sim). Quando a energia não passa,
esse resultado é igual a 0 (não).
O processador permite que os cálculos binários sejam realizados e,
a partir desse ponto, entra em jogo o sistema operacional que transfor-
ma tudo o que você faz nessa linguagem binária, a qual é passada para
o software, podendo, por sua vez, fazer o que você quer.
Para auxiliar no entendimento desse processo binário, sugerimos o artigo
Aritmética de números binários e suas relações com circuitos lógicos, dos auto-
res Rafael Pinheiro Leite e Prof. Dr. Matheus da Silva Menezes.
Acesso em: 31 maio 2021.
https://repositorio.ufersa.edu.br/bitstream/prefix/5854/1/RafaelPL_ART..pdf
Artigo
18 Matemática para Computação
Para elaborar um algoritmo numérico, precisamos de algumas eta-
pas anteriores.
Exemplo:
Queremos encontrar a divisão
exata de a
2
�, com a > 0 usando
apenas as quatro operações
fundamentais.
Definição do
problema
É a primeira etapa.
Como o próprio
nome sugere, é preciso
compreender o que se deseja
estruturar e as possibilidades
de resposta.
Modelagem
A segunda etapa é
por meio de uma
formulação matemática.
Transformamos o problema real em
um problema matemático.
Exemplo:
Usando o exemplo anterior, escrevemos
a {2x�|�x *� � � }
Assim, modelamos a definição do problema
colocando as características matemáticas
necessárias para resolvê-lo. Nesse caso,
identificamos que a precisa ser um número
par para que tenhamos divisão exata.
Solução numérica
Nesta terceira etapa escolhemos
o método numérico apropriado
para resolver o modelo
matemático. É nesse ponto que
precisamos avaliar os métodos
existentes e escolher aquele que
resulte em menor erro numérico.
A escrita do algoritmo entra
nessa etapa e é idealizada
aplicando as possibilidades
do método escolhido.
Kh
vo
st
/S
hu
tte
rs
to
ck
ol
eg
ga
nk
o/
Sh
ut
te
rs
to
ck
TK
1
98
0/
Sh
ut
te
rs
to
ck
da
vo
od
a/
Sh
ut
te
rs
to
ck
As duas últimas etapas não serão abordadas neste capítulo, visto
que não é escopo desta obra trabalhar com as linguagens de progra-
mação, entretanto, para que possamos registrar os passos seguintes à
escrita do algoritmo, temos:
Por que estudar matemática? 19
Codificação
do algoritmo
Processamento
do programa
A transformação
do algoritmo para
a linguagem de
programação escolhida.
Implementação do
algoritmo na linguagem de
programação escolhida.
Nesse caso, o programa será
escrito em um arquivo para
ser executado.
ST
RI
PB
AL
L/
Sh
ut
te
rs
to
ck
ST
RI
PB
AL
L/
Sh
ut
te
rs
to
ck
Kh
vo
st
/S
hu
tte
rs
to
ck
Observe que a idealização de um algoritmo numérico passa pela
etapa de modelagem do problema, que só é possível com o conheci-
mento matemático sobre esse conteúdo. Já na etapa de solução numé-
rica, além do entendimento dos métodos numéricos disponíveis para a
resolução do modelo, é preciso analisar os possíveis erros obtidos com
essa escolha. Essa etapa é otimizada quando entendemos os tipos de
erros que podem ser gerados pelo computador.
Muitos algoritmos usam as chamadas relações de recorrência para
realizar seus cálculos e convergir para a resposta desejada. Vamos en-
tender esse conceito na sequência.
1.3 Relações de recorrência
Vídeo A base da maior parte dos algoritmos matemáticos vem do conceito
de relação de recorrência. Uma relação de recorrência é uma técnica
matemática que nos auxilia na definição de sequências, conjuntos, ope-
rações ou algoritmos. Para que tenhamos uma fórmula de recorrência,
20 Matemática para Computação
precisamos analisar as características do problema e escrever uma re-
gra que o represente.
Com o intermédio dessa regra, podemos calcular qualquer termo
em função dos antecessores. Nesta seção, vamos trazer como objeto
para entendermos as relações de recorrência a famosa fórmula de re-
corrência de Fibonacci.
Leonardo de Pisa, mais conhecido como Fibonacci, que significa fi-
lho do Bonacci, descreveu sua sequência pela primeira vez em seu livro
Liber Abaci, em 1202, a fim de modelar um problema relacionado com
o crescimento de uma população de coelhos.
Fibonacci desejava descrever a quantidade de casais em uma po-
pulação de coelhos após n meses (Figura 3), partindo dos seguintes
pressupostos (ZAHN, 2011):
1. nasce apenas um casal no primeiro mês;
2. casais amadurecem sexualmente após o segundo mês de vida;
3. assumimos que não há problemas genéticos no cruzamento
consanguíneo;
4. todos os meses, cada casal dá à luz um novo casal;
5. os coelhos nunca morrem.
Figura 3
Sequência de casais em
uma população de coelhos
M
ag
ic
le
af
/S
hu
tte
rs
to
ck
Por que estudar matemática? 21
O que ele encontrou foi a fórmula de recorrência – uma função
aritmética – da definição a seguir:
Definição 1
Seja uma sequência de Fibonacci, formada por n termos e denotada por fn. Para
calcularmos o n-ésimo termo dessa sequência fazemos:
f
n �
�
�
� �
�
�
�
�
�
� �
0 0
1 1
11 2
, � �
,� �
, � ��
se n
se n
f f se nn n
Com essa função podemos montar a sequência de Fibonacci e des-
cobrir quantos coelhos foram gerados em cada mês. Vamos exemplifi-
car essa definição.
Exemρlo 3
Utilizando a fórmula de recorrência
f
f f
n
�n n
�
�
�
� �
�
�
�
�
�
� �
0 0
1 1
11 2
,� �
,� ��
� � ,�� � �
se n
se n
se n
Temos que:
• f5 = f5–1 + f5–2 = f4 + f3 = 5;
• f10 = f10–1 + f10–2 = f9 + f8 = 55.
Os primeiros números da sequência de Fibonacci são: 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89.
Percebemos com esse exemplo a usabilidade das relações de re-
corrência em processos matemáticos, principalmente nos processos
que precisam ser transformados em algoritmos, para que possam ser
programados.
Para saber mais sobre as
relações de recorrência e
a sequência de Fibonacci,
sugerimos dois vídeos do
canal Programa de Inicia-
ção Científica da OBMEP:
• Aula 01 - Sequências definidas
por recorrências – Disponível
em: https://www.youtube.com/
watch?v=S9zDoNAr3d4. Acesso
em: 31 maio 2021.
• Indução Matemática - Aula 6 -
Sequência de Fibonacci. Disponível
em: https://www.youtube.com/
watch?v=QVlTuInyZKk. Acesso
em: 31 maio 2021.
Vídeo
https://www.youtube.com/channel/UC5azyx8w7Y5qzASuxDSseOw
https://www.youtube.com/channel/UC5azyx8w7Y5qzASuxDSseOw
https://www.youtube.com/watch?v=S9zDoNAr3d4
https://www.youtube.com/watch?v=S9zDoNAr3d4
https://www.youtube.com/watch?v=QVlTuInyZKk
https://www.youtube.com/watch?v=QVlTuInyZKk
22 Matemática para Computação
1.4 Conceito de função no aspecto
computacionalVídeo
Na matemática, uma função é uma “regra” que associa a cada ele-
mento x ∈ X um único elemento y = f(x) ∈ Y (GUIDORIZZI, 2018). Temos
que X e Y são conjuntos que podem conter elementos previamente de-
finidos, por exemplo, números naturais, reais etc., ou outros tipos de
elementos, como chapéus, aves, laços etc.
Assim, desde que consigamos relacionar, por meio de uma regra,
um elemento do conjunto X com um único elemento do conjunto Y,
podemos dizer que estamos trabalhando com uma função.
Na matemática, dizemos que essa regra é uma lei matemática.
A notação usada para essa definição é dada por:
f: X → Y
Definição 2
No aspecto computacional, uma função pode ser escrita por meio da soma de
um número finito de parcelas.
Observe no exemplo a seguir como podemos representar uma fun-
ção por meio de somas de infinitas parcelas. Esse é um processo mate-
mático conhecido como séries de funções. Computacionalmente não é
possível manusear somas infinitas, mas ao sintetizarmos a série, temos
a representação da função com um erro aceitável.
Exemρlo 4
Uma série geométrica da forma
1 + x2+ x4 + x6 + ...
Representa uma função escrita como
f x
x
� � �
�
1
1 2
Até mesmo as funções trigonométricas podem ser escritas por meio
de uma soma infinita de parcelas, como vemos no exemplo 5.
Por que estudar matemática? 23
Exemρlo 5
senx x x x x ��� �
�
�
��
�
�
�� �
�
�
��
�
�
�� �
�
�
��
�
�
�� ��
3 5 7
3 5 7! ! !
cos
! ! !
x x x x� �
�
�
��
�
�
�� �
�
�
��
�
�
�� �
�
�
��
�
�
�� ��1 2 4 6
2 4 6
Essa forma de representarmos as funções é também chamada
de série e comumente estudada em disciplinas de Cálculo Avançado.
Essa é uma maneira de pensarmos em funções quando tratamos dos
aspectos computacionais.
Uma segunda abordagem do aspecto computacional das funções é
a possibilidade de considerá-las como ferramentas de cálculo dentro
de algoritmos. Por exemplo, na linguagem de programação PythonTM
(Figura 4), uma função é uma sequência de comandos que executa al-
guma tarefa. Essa sequência é geralmente nomeada, para que a função
possa ser “chamada” sempre que necessária.
Figura 4
Função cone em PythonTM
#A is height B is radius
def cone (a, b):
formula = (3.14 * .33 *a)*(b * b)
return formula
Aa
æ
/W
ik
im
ed
ia
C
om
m
on
s
Consideremos o cálculo do volume de uma esfera, em que seu raio
é conhecido. O exemplo a seguir mostra a estrutura lógica que permite
realizar o cálculo desse volume, considerando r como uma variável que
pode assumir qualquer valor real.
Exemρlo 6
Crie uma função para o cálculo do volume de uma esfera de raio r.
Solução
r é real
def esfera(r)
Para conhecer um pouco
mais das possibilidades
de aplicação de séries
numéricas usadas para
representar funções, su-
gerimos o vídeo Séries de
Potências no Computador.
Disponível em: http://eaulas.usp.br/
portal/video.action?idItem=7701.
Acesso em: 31 maio. 2021.
Vídeo
Quer saber mais sobre
funções em PythonTM?
Sugerimos o material
Funções.
Disponível em: https://panda.ime.
usp.br/pensepy/static/pensepy/
05-Funcoes/funcoes.html. Acesso
em: 31 maio. 2021.
Saiba mais
http://eaulas.usp.br/portal/video.action?idItem=7701
http://eaulas.usp.br/portal/video.action?idItem=7701
https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html
https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html
https://panda.ime.usp.br/pensepy/static/pensepy/05-Funcoes/funcoes.html
24 Matemática para Computação
formula = 4/3 *(3,14)*r^3
return formula
Agora podemos usar essa função. Assim, se escrevermos esfera(2),
teremos como retorno o valor formula = 33 37
75
Entretanto, nos dois sentidos, podemos perceber o princípio fun-
damental de uma função matemática, que é o de ser uma regra que
vincula dois conjuntos de dados diferentes.
1.5 Diferenças entre problemas
qualitativos e quantitativosVídeo
Um problema é dito qualitativo quando os dados usados para re-
solver o modelo são dados qualitativos, ou seja, são baseados em cará-
ter subjetivo, em que são usadas narrativas escritas ou faladas.
Uma pesquisa qualitativa pode reunir informações como o nome
das pessoas que foram avaliadas em um determinado estudo, o estilo
de vida desse grupo de pessoas, as preferências alimentares, hobbies,
dentre outras informações que, em geral, são fornecidas por meio de
narrativas, questionários abertos, entrevistas, observações etc., e que
não são codificadas usando um sistema numérico.
Uma pesquisa qualitativa pode ser dividida em pesquisa nominal ou
ordinal. Como a própria nomenclatura sugere, uma pesquisa nominal
é aquela em que temos como resposta à pesquisa “nomes”, sendo que
não é possível ordenar tais respostas. Por exemplo, uma pesquisa que
possui o campo “sexo”, terá como resposta “masculino” ou “feminino”.
Esse tipo de resposta pode ser quantificado, contudo não conseguimos
colocar ordem de importância para tal.
Ainda no campo da pesquisa qualitativa, podemos ter dados ordi-
nais. Nesse caso, é possível categorizar as variáveis em relação a de-
terminado grau para cada categoria. Por exemplo, uma pesquisa que
procura analisar o grau de instrução de seus participantes, pode conter
a variável “nível de escolaridade”, como ensino fundamental e ensino
médio. É possível construir uma classe para cada grau de escolaridade,
e até quantificar os participantes em cada uma dessas, mas a variável
continua tendo um teor puramente qualitativo.
Por que estudar matemática? 25
O interesse quando modelamos um problema com o auxílio de pes-
quisas quantitativas é identificar e compreender os fenômenos através
de dados numéricos.
Por exemplo, se desejamos saber a quantidade de pessoas que to-
maram determinado remédio ou votaram em determinado candidato,
precisaremos realizar pesquisas quantitativas.
Podemos pensar na escolha de um método ou outro da seguinte
forma:
• Método qualitativo: geralmente é utilizado para categorizar uma
determinada situação, classificar problemas e gerar hipóteses etc.
• Método quantitativo: é utilizado, como o próprio nome remete,
a quantificar objetos. Os métodos quantitativos são muito usa-
dos na estatística. Em geral, adotam-se questionários que permi-
tem a contagem das variáveis pesquisadas.
O que caracteriza um método como quantitativo ou qualitativo são
as variáveis que ele apresenta. Assim, chamamos de variáveis quanti-
tativas as que possuem características que podem ser quantificadas,
isto é, medidas em determinada escala quantitativa. Por esse motivo,
são representadas numericamente e podem ser divididas em duas ca-
tegorias: discretas ou contínuas.
As variáveis discretas são representadas por valores (números) in-
teiros. Alguns exemplos são: quantidade de filhos, de pessoas em de-
terminado local e de produtos na geladeira.
As variáveis contínuas recebem valores em uma escala contínua,
em que podem estar presentes valores representados por frações e
decimais (finitos ou infinitos). É comum a necessidade de instrumen-
tos de medição para avaliar uma variável quantitativa contínua, como
balanças, réguas, relógios e outros instrumentos de medição. Alguns
exemplos desse tipo de variável são: idade, peso, altura etc.
As variáveis qualitativas, ao contrário, não são representadas por
valores que podem ser quantificados. Elas representam categorias, ou
seja, algum tipo de classificação para pessoas, objetos ou situações, e
podem estar subdivididas em duas categorias: nominais ou ordinais.
As variáveis nominais não exigem ordenação, por exemplo: sexo,
cor dos olhos, religião, profissão etc. Já as variáveis ordinais exigem
ordenação dos dados coletados. São exemplos: classe social (A, B, C)
e escolaridade (1º ano, 2º ano, 3º ano).
Tanto um problema qualitativo como um problema quantitativo
pode ser investigado para que seja “resolvido” com o auxílio de um al-
goritmo executado computacionalmente. Mas é na pesquisa quantita-
tiva que esses resultados têm ganhado destaque.
A ciência de dados (Figura 5), considerada uma ciência estatística,
teve seu início com a ideia de podermos resolver problemas matemáti-
cos de maneira computacional.
Figura 5
Áreas da ciência de dados
CIÊNCIA DE DADOS
Megadados Classificação
de dados
Análise de dados Estatística Solucionador Tomada de
decisão
Conhecimento
aberto
bu
ffa
lo
bo
y/
Sh
ut
te
rs
to
ck
.
Ela pode ser definida como um conjunto de ferramentas e métodos
que nos permitem analisar, visualizar e tomar decisões com base em
dados (RAMOS, 2021).
É aqui que a matemática e a computação, novamente, se encon-
tram. A quantidade de dados gerados por ferramentas como Google,
Netflix, Twitter, Uber, entre outras que usamos no nosso dia a dia, é
imensa. Para coletar, organizar e aplicar em modelos que deem um
retorno para essas empresas em forma de resultado financeiro, é ne-
cessário que diversas áreas da matemática sejam envolvidas, dentre
elas encontra-se a estatística, talvez a mais utilizada nesse sentido.
Diana_Karch/Shutterstock
Rede neural
2626 Matemática para ComputaçãoMatemática para Computação
https://oestatistico.com.br/decisoes-big-data-feeling-better-data/https://oestatistico.com.br/decisoes-big-data-feeling-better-data/
Por que estudar matemática? 27
De acordo com Ramos (2021), “o chamado ‘cientista de dados’ é
o profissional responsável por aplicar técnicas, modelos, tecnologias
e processos para extrair informação relevante dos dados. Tudo isso
com muita estatística e programação aplicada”.
Dessa forma, pensar em algoritmos que possibilitam o uso des-
ses dados é fundamental para o crescimento das empresas. Esses
algoritmos poderão, por exemplo, estar vinculados ao marketing digi-
tal, fazendo com que dados quantitativos e qualitativos gerem lucro.
Nesse ponto, entram os chamados algoritmos de inteligência artifi-
cial. Um dos quesitos necessários para esse tipo de algoritmo é que ele
processe um grande volume de dados quantitativos ou qualitativos.
A diferença desse tipo de algoritmo para os demais é a possibi-
lidade de se aplicar um “fator de decisão”, ou seja, a existência de
variáveis randômicas ou condicionadas, dentro de um domínio deter-
minado, que permitirão que os resultados não sejam únicos, e sim ter
uma gama de possibilidades definidas para o contexto aplicado.
Nesse ponto, podemos ter algoritmos construídos com o uso de
diferentes funções. É possível trabalhar em diferentes camadas e com
funções matemáticas específicas para cada camada de dados.
Perceba que, mesmo nesse quesito, o domínio sobre o algoritmo
está na mão do programador. É ele quem determina o que serão es-
ses “fatores de decisão” e como será seu comportamento matemático
para que o cálculo se torne randomizado. A compreensão da mate-
mática levará à obtenção dos resultados desejados.
CONSIDERAÇÕES FINAIS
Neste capítulo, trouxemos uma pequena parte do gigantesco mundo
da matemática aplicada à computação, à qual nos referimos como mate-
mática computacional.
As possibilidades são enormes, a depender da área almejada. É possí-
vel trabalhar desde processos de otimização de redes até a bela área da
programação gráfica, passando pelo rico campo da inteligência artificial
e da ciência de dados. Independentemente da área escolhida, a necessi-
dade da compreensão da matemática que envolve todos esses cálculos é
imprescindível para sua correta implementação.
Desse modo, esperamos que você se sinta motivado a seguir nesse
caminho que relaciona essas duas ciências: matemática e computação.
28 Matemática para Computação
ATIVIDADES
Sabendo que um algoritmo é compreendido como um processo que
mostra detalhadamente os métodos necessários para a resolução de
uma atividade, e que podemos pensar nessa estrutura em formato de
pseudocódigo como estrutura inicial, descreva um pseudocódigo para o
cálculo da expressão numérica 1 + 3(5 + 1).
Atividade 1
Descreva o modelo matemático que pode ser utilizado para representar
a definição do problema a , para a > 0, usando apenas as quatro
operações aritméticas.
Atividade 2
Uma pesquisa foi realizada coletando dados referentes à altura de alu-
nos de uma sala de aula. Esse tipo de dado é qualitativo ou quantitativo?
Justifique.
Atividade 3
REFERÊNCIAS
BIM, S. A. A vida de Ada Lovelace. Porto Alegre: Sociedade Brasileira de Computação, 2018.
BROMLEY, A G. Charles Babbage’s Analytical Engine, 1838. Annals of the History of
Computing, v. 4, n. 3, 1982. Disponível em: http://athena.union.edu/~hemmendd/Courses/
cs80/an-engine.pdf. Acesso em: 31 maio 2021.
CAMPOS FILHO, F. F. Algoritmos numéricos: uma abordagem moderna de Cálculo Numérico.
São Paulo: LTC, 2007.
GUIDORIZZI, H. L. Um curso de cálculo. 6. ed. v. 1. Rio de Janeiro: LTC, 2018.
KHOURY, J. Application to a probleme of Fibonacci. Disponível em: http://aix1.uottawa.
ca/~jkhoury/fibonacci.htm. Acesso em: 31 maio 2021.
RAMOS, R. Ciência de dados: uma breve história. O Estatístico. Disponível em: https://
oestatistico.com.br/ciencia-de-dados-uma-breve-historia/. Acesso em: 31 maio 2021.
SIMÕES, I. Ada Lovelace desafiou o machismo e se tornou a primeira programadora
da história. Darkside. Disponível em: https://darkside.blog.br/ada-lovelace-desafiou-o-
machismo-e-se-tornou-a-primeira-programadora-da-historia/. Acesso em: 31 maio 2021.
ZAHN, M. Sequência de Fibonacci e o Número de Ouro. Rio de Janeiro: Ciência Moderna, 2011.
http://aix1.uottawa.ca/~jkhoury/fibonacci.htm
http://aix1.uottawa.ca/~jkhoury/fibonacci.htm
Noções sobre sistemas de numeração 29
2
Noções sobre sistemas
de numeração
Você já parou para pensar que o sistema de numeração que usamos
na atualidade passou por diversas transformações ao longo da história
para chegar ao que ele é hoje?
Além disso, por muito tempo ele não foi único. Diferentes civilizações
construíram seus próprios sistemas de numeração com os conhecimen-
tos que tinham na época.
E você sabia que esse sistema numérico que usamos, o indo-arábico,
fortemente desenvolvido, embasado e com toda a estrutura matemática
moderna construída sobre ele, é deixado de “lado” quando pensamos em
cálculos realizados por um computador?
Além do sistema de numeração adotado, quando o computador é usa-
do ainda precisamos admitir propagações de erro. Sim, o computador
comete muitos erros numéricos.
Com o estudo deste capítulo, você será capaz de:
• compreender os diferentes sistemas de numeração;
• identificar erros numéricos e como interpretá-los;
• caracterizar as diferentes representações numéricas
computacionais;
• compreender o conceito de erro numérico.
Objetivos de aprendizagem
2.1 Sistemas de numeração
Vídeo Um dos sistemas de numeração mais antigos foi encontrado, por
meio de pesquisas arqueológicas, na Tchecoslováquia, Europa, em 1937,
com data entre aproximadamente 35000 a.C. e 20000 a.C. Basicamente,
30 Matemática para Computação
os pesquisadores encontraram um osso (tíbia) de lobo jovem com mar-
cações unitárias feitas por meio de traços (cortes transversais), na forma:
I II III IIII
Ao todo eram 57 traços, sendo os primeiros 25 agrupados de 5 em 5
(ALMEIDA, 2011).
Essa descoberta nos mostra a necessidade da contagem e possibili-
ta discutir sobre os sistemas de numeração.
O tipo de contagem observada nesse estudo é dita aditiva, em que,
para se ter o próximo número, basta acrescentar uma marcação (|).
Além disso, o sistema de numeração foi composto de apenas um sím-
bolo, sendo chamado de sistema de numeração de base 1.
A obra Através do espelho e o que Alice encontrou por lá, escrita em
1871 pelo matemático Lewis Carroll (1832-1898) e traduzida para mui-
tos idiomas – inclusive o português –, traz um diálogo entre a rainha
Branca e Alice, que demonstra a dificuldade que teríamos se o sistema
de numeração de base 1 fosse adotado atualmente. Alice fala para a
rainha que aulas servem para nos ensinar a fazer contas, e a rainha
lhe pergunta: “e sabe Adição? Quanto é um mais um mais um mais um
mais um mais um mais um mais um mais um mais um?”. Alice lhe res-
ponde: “não sei. Perdi a conta” (CARROLL, 2013, p. 186).
Na história da matemática identificamos diversas civilizações que
adotaram sistemas ditos aditivos.
Mas como exatamente (algebricamente) podemos definir um sistema
aditivo?
Vamos assumir que b é um número natural, tal que determinado
sistema aditivo está escrito na base b. Assim, temos duas condições
que precisam ser respeitadas:
1 O sistema deverá ter b símbolos para sua representação numérica,
ou seja, teremos a1, a2, ..., ab símbolos para representar os números
de um até b. Esses números deverão ser representados em ordem
crescente.
Caso tenha se interessado
pelas obras de Carroll e
queira saber um pouco
mais sobre esse assunto,
sugerimos o texto Lewis
Carroll e a matemática
do País das Maravilhas,
publicado pela Sociedade
Brasileira de Matemática.
Disponível em: https://www.
sbm.org.br/noticias/lewis-carroll-
e-a-matematica-do-pais-das-
maravilhas. Acesso em: 2 jun. 2021.
Leitura
https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas
https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhashttps://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas
https://www.sbm.org.br/noticias/lewis-carroll-e-a-matematica-do-pais-das-maravilhas
Noções sobre sistemas de numeração 31
2 Deve-se obedecer a regra do sucessor, que implica assumir que
se um número termina em ai, com i ≠ b, então a representação de
seu sucessor será obtida por meio da substituição de ai por ai+1.
Caso a representação de um número termine em ab, seu sucessor
será obtido acrescentando a1 à representação dada.
Entre alguns dos sistemas aditivos mais importantes na história, en-
contram-se o sistema hieroglífico (Figura 1), desenvolvido pelos egíp-
cios por volta de 3400 a.C., e o sistema de numeração da antiga Grécia,
desenvolvido por volta do século IV a.C.
Figura 1
Sistema numeral egípcio
Numerais egípcios
Sistema numérico hieroglífico egípcio
Sistema egípcio de numeração hierática
Si
dh
e/
Sh
ut
te
rs
to
ck
No entanto, foi com o sistema chamado posicional que a matemáti-
ca começou a se desenvolver com maior rapidez.
32 Matemática para Computação
Não se tem consenso de qual foi a civilização que idealizou primeiro o
chamado sistema de numeração posicional, em que se encontram o nosso
sistema posicional de base decimal e o sistema binário computacional,
mas o que se sabe é que, para esse tipo de construção, foi necessário
o desenvolvimento lógico da ideia de agrupamentos entre os números.
Nesse contexto histórico, identificou-se que os hindus praticaram o
sistema posicional decimal e tiveram a preocupação de construir uma
representação visual dele, que pudesse ser transferida de maneira
escrita. Entretanto, foram os árabes que divulgaram esse sistema de
numeração pelo ocidente, e por esse motivo o chamamos de sistema
indo-arábico.
Figura 2
Evolução do sistema posicional decimal
Hindu – 300 a.C.
Hindu – 500 d.C.
Árabe – 900 d.C.
Árabe – (Espanha) 1000
d.C.
Italiano – 1400 d.C.
Hoje
Fonte: Elaborada pela autora.
Um sistema de numeração posicional é aquele em que a posição
na qual o algarismo se encontra modifica o seu valor, ou seja, no caso
do sistema posicional de base decimal (o sistema que usamos), se o
algarismo 1 estiver na posição (casa) da unidade, ele vale 1 unidade. Se
o mesmo algarismo estiver na posição da dezena (casa da dezena), ele
vale 10 unidades. Se estiver na posição da centena, vale 100 unidades,
e assim sucessivamente.
Usando o sistema numérico posicional decimal, a Tabela 1 apre-
senta alguns exemplos com diferentes posicionamentos para o al-
garismo 1.
Noções sobre sistemas de numeração 33
Tabela 1
Posição do algarismo 1 em relação ao valor numérico obtido
Classes Milhões Milhares Unidades simples
Ordens c d u c d u c d u
1
1 0 0 0 0
1 0 0 0 0 0 0 0 0
Fonte: Elaborada pela autora.
Um sistema de numeração posicional pode ser definido de maneira
geral (algébrica), assim como fizemos para os sistemas posicionais.
Nesse contexto, usaremos b ∈ ℕ como uma base qualquer. Assim, para
construir um sistema posicional de base b, precisamos garantir duas con-
dições. Por isso, considere b ≠ 1. Inicialmente, precisamos determinar b
símbolos, sendo um desses destinado a representar a casa vazia (zero) e
os demais destinados a representar os números de 1 a (b – 1).
1 Se o número a ser representado tem como unidade um dos
algarismos que representam 0, 1, ..., (b – 2), ele terá um sucessor
substituindo-se esse algarismo por seu sucessor, apresentado na
ordem crescente, que será (b – 1).
2 Se o número a ser representado tem como unidade o algarismo
que representa (b – 1), ele já é o último algarismo dessa base. Nesse
caso a representação do sucessor será obtida substituindo-se esse
algarismo por zero e, em seguida, aplicando-se recorrentemente os
itens 1 e 2 dessa regra à casa seguinte.
3 Se a casa seguinte for vazia, considera-se como se ela tivesse o
valor zero.
Atualmente, o sistema de numeração posicional de base dez (siste-
ma indo-arábico), em que a posição do algarismo indica a potência de
10 que o dígito representa, é usado em todo o mundo, sendo utilizado
de maneira tão intuitiva, como uma criança pequena que usa os dedos
para contar, que é difícil imaginar qualquer tipo de construção numéri-
ca sem essa formatação.
34 Matemática para Computação
Observe o exemplo de como decompomos um número no sistema
posicional decimal por meio da representação geral enunciada.
Exemρlo 1
x = (1957)10 = 1 · 10
3
+ 9 · 10
2 + 5 · 101 + 7 · 100
Note que, com esse formato, fica evidente o uso da chamada base
decimal. Essa formatação será adotada para a escrita das próximas ba-
ses que estudaremos nesta obra.
Queremos conceituar e identificar as características não só para o
sistema posicional decimal, mas para outros sistemas posicionais que
são usados na matemática e na computação, permitindo, assim, uma
visão do cálculo numérico envolvido nesse processo.
Definição 1
Dados um número natural com b > 1 e o conjunto de símbolos {±, 0, 1, 2, ...,
b – 1}, a sequência de símbolos
(dndn–1 ... d1d0, d-1d-2 ...)b
representa o número positivo
dn · b
n + dn–1 · b
n–1 + ... + d0 · b
0
+ d–1 · b
–1 + d–2 · b
–2 + …
Para representar números negativos, usamos o símbolo – à esquer-
da do numeral, conforme exemplificamos a seguir.
Exemρlo 2
x = (1.957,897)10
x = 1 · 103 + 9 · 102 + 5 · 101 + 7 · 100 + 8 · 10–1 + 9 · 10–2 + 7 · 10–3
x = 1.000 + 900 + 50 + 7 + 0,8 + 0,09 + 0,007
Portanto, percebemos que, além da escolha do sistema de numera-
ção (aditivo ou posicional), há muitas representações distintas em rela-
ção à quantidade de algarismos envolvida em cada um desses modelos
(bases adotadas).
Noções sobre sistemas de numeração 35
Na próxima seção, focamos nos sistemas posicionais mais utilizados
pela matemática moderna e pela matemática computacional.
2.2 Representação numérica
Vídeo Entender a representação numérica do sistema escolhido não só
possibilita sua compreensão, mas viabiliza realizar operações com o
tipo de numeração escolhido, além de permitir verificar possíveis erros
cometidos nos cálculos.
Como nosso foco é trabalhar com a matemática para a computa-
ção, dedicaremos esta seção à representação numérica implícita nas
máquinas digitais eletrônicas, ou seja, nos computadores.
Assim, o primeiro sistema que vamos discutir é o chamado sistema
de numeração posicional de base dois ou base binária.
2.2.1 Sistema binário
Quando pensamos em um sistema de numeração que permita
realizar operações no computador (chamamos de computador as má-
quinas digitais eletrônicas), a base utilizada é a base dois. Seu uso está
diretamente vinculado ao desenvolvimento das máquinas digitais.
Durante muitos séculos se creditou a Gottfried Wilhelm Leibniz
(1646-1716) a idealização da base binária.
Para saber mais sobre Leibniz e a relação desse matemático com a base da
computação, sugerimos a leitura de Leibniz e nosso mundo digital, de Gilberto
Garbi, publicado pela Revista do Professor de Matemática (RPM).
Acesso em: 2 jun. 2021.
https://www.rpm.org.br/cdrpm/84/1.html
Artigo
Contudo, pesquisas recentes demonstram que
em uma pequena ilha da Polinésia, séculos an-
tes da idealização de Leibniz, o povoado de
Mangareva já utilizava a base binária para rea-
lizar cálculos que permitiam a comercialização
de seus produtos.
Gottfried Wilhelm
Leibniz
Nicku/Shutterstock
36 Matemática para Computação
Ao analisar a pesquisa dos cientistas noruegueses Andrea
Bender e Sieghard Beller, do departamento de ciência psicossocial
da Universidade de Bergen, na Noruega, Javier Sampedro (2013)
descreve que os pesquisadores
mostram agora como os habitantes da Mangareva não só inven-
taram o sistema para contar peixes, frutas, cocos, polvos e outros
bens de diferente valor em suas transações comerciais, como tam-
bém que isso conduziu a uma aritmética binária que teria mere-
cido a aprovação do Leibniz por sua simplicidade e naturalidade.
Dos fatos históricos, sabemos que a base binária foi deixa-da de lado até mesmo por Leibniz, e apenas séculos após sua
morte, em 1841, foi redescoberta pelo matemático George
Boole (1815-1864), o qual desenvolveu a chamada álgebra
booleana, que permitiu o desenvolvimento do computador
digital eletrônico, imprescindível para o desenvolvimento em
praticamente todas as áreas do conhecimento na atualidade.
O computador lida com grandezas representadas como se-
quências de bits (base 2).
Quando precisamos transcrever um método matemático para um mé-
todo numérico, ou seja, para a matemática computacional, precisamos,
em primeiro lugar, compreender como um computador manipula as in-
formações – no nosso caso, as informações são numéricas e simbólicas.
Toda informação manipulada por um computador é representada
como uma sequência de bits (binary digits). Ao agrupar 8 bits, temos 1
byte; quando agrupados (Figura 3), os bytes darão origem aos kilobytes,
megabytes, gigabytes, terabytes etc. – termos comumente usados na
computação e no nosso dia a dia.
Figura 3
Sequência de bits
Ra
hi
m
ov
E
m
in
/S
hu
tte
rs
to
ck
Medidas de informação eletrônica
Célula de memória
de 8 bits
0 1 0 1
1 0 1 0
1 byte = 8 bit
1 KB = 8.192 bit
1 KB = 1.024 byte
1 MB = 1.024 KB
1 GB = 1.024 MB
1 TB = 1.024 GB
KB – kilobyte
MB – megabyte
GB – gigabyte
TB – terabyte
Sugerimos a leitura na
íntegra do texto Um
sistema binário inventado
na Polinésia séculos antes
de Leibniz, do autor Javier
Sampedro.
Disponível em: https://brasil.
elpais.com/brasil/2013/12/16/
sociedad/1387215405_275511.
html. Acesso em: 2 jun. 2021.
Leitura
George Boole
Wd
wd
/W
ikim
edi
a C
omm
ons
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
Noções sobre sistemas de numeração 37
Um bit aceita duas respostas possíveis:
• 0 – não, falso, desligado;
• 1 – sim, verdadeiro, ligado.
Na área eletrônica, interpreta-se isso como passagem de ener-
gia (sim) ou sem passagem de energia (não). Essa leitura do código
binário é feita milhares de vezes por segundo.
Esse tipo de representação, também chamado de representação
binária, matematicamente pode ser traduzido como um sistema de
numeração na base dois.
Exemρlo 3
Assim, para a codificação de um número natural entre 0 e 255,
por exemplo, seriam suficientes 8 bits, pois 28 = 256. Desse modo,
para representá-los, restaria apenas atribuir valores 0 ou 1.
O número natural 255 será representado em uma sequência de
bits (sequência binária) por 11111111.
Mais adiante explicaremos os processos de conversão.
Como demonstramos, o sistema de numeração na base dois,
também chamado de binário na área da computação, tem seus al-
garismos reconhecidos e representados por meio dos bits (binary
digits). Já identificamos que um bit pode assumir dois valores dis-
tintos: 0 ou 1.
Embasados nos conhecimentos adquiridos até o momento so-
bre base binária, começamos a trabalhar com as mudanças de
base.
Com essa finalidade, o exemplo a seguir apresenta uma mudan-
ça da base binária para a base decimal, tendo como ideia principal
o tipo de conversão adotada pelo computador.
fli
gh
t o
f i
m
ag
in
at
io
n/
Sh
ut
te
rs
to
ck
Representação do código
binário pelos botões com
símbolos I (ligado) e O
(desligado).
Figura 4
0 ou 1
Para conhecer mais sobre
a relação entre bits e
bytes e a sucessão de
agrupamentos, sugerimos
a leitura de Qual a diferen-
ça entre Kilobyte, Megabyte,
Gigabyte e Terabyte?, pu-
blicado no site da Copel
Telecom.
Disponível em: https://www.
copeltelecom.com/site/blog/
kilobyte-megabyte-gigabyte-
terabyte/. Acesso em: 2 jun. 2021.
Leitura
https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/
https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/
https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/
https://www.copeltelecom.com/site/blog/kilobyte-megabyte-gigabyte-terabyte/
38 Matemática para Computação
Exemρlo 4
Seja x = 1001,101, então
1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 + 1 · 2–1 + 0 · 2–2 + 1 · 2–3
= 8 + 0 + 0 + 1 + 0,5 + 0 + 0,125
= 9,625
Portanto, (1001,101)2 = (9,625)10.
Note que no exemplo utilizado respeitamos a posição de cada um
dos elementos e fizemos a conversão, em primeiro plano, assumindo o
valor de cada posição e, na sequência, somando esses resultados.
Esse é o processo que será adotado para as bases que veremos na
sequência.
2.2.2 Sistema quaternário
No sistema quaternário a base b é igual a 4 e, portanto, temos o
conjunto de algarismos {0, 1, 2, 3}.
Exemρlo 5
Seja x = (301,2)4, então
3 · 42 + 0 · 41 + 1 · 40 + 2 · 4–1 = 48 + 0 + 1 + 0,5 = 49,5
Portanto, (301,2)4 = (49,5)10.
Mais adiante veremos como converter uma base decimal para uma
base qualquer.
Na sequência, apresentamos a base hexadecimal, ou seja, uma base
formada por 16 algarismos.
2.2.3 Sistema hexadecimal
O estudo do sistema hexadecimal auxilia no processo de represen-
tação de sequências maiores de bits, por exemplo, com 16 ou 32 bits.
Se b > 10, usamos as letras A, B, C, ... para denotar A = 10, B = 11, C = 12, ...
Para ficar claro esse sistema, vamos exemplificar.
Noções sobre sistemas de numeração 39
Exemρlo 6
Se temos b = 16, ou seja, o conjunto de algarismos {0, 1, 2, 3, 4, 5, 6,
7, 8, 9, A, B, C, D, E, F}, e queremos converter o número x = (E2AC)16 para
a base decimal, fazemos:
(E2AC)16 = 14 · 16
3 + 2 ·162 + 10 ·161 + 12 · 160
(E2AC)16 = 57.344 + 512 + 160 + 12 = 58.028
A base hexadecimal também é amplamente usada na computação.
Você já ouviu falar do tripleto hexadecimal, também chamado de
web color (Figura 5)?
O tripleto hexadecimal recebe esse nome porque é uma combina-
ção de 3 bytes, pois cada cor formada possui três duplas escritas em
formato hexadecimal. Cada dupla representa uma cor, sendo elas: ver-
melho, verde e azul (RGB).
A variação da combinação hexadecimal no tripleto dará origem às
demais cores.
Figura 5
Web color
R.
A
. N
on
en
m
ac
he
r/
W
ik
im
ed
ia
C
om
m
on
s
40 Matemática para Computação
Exemρlo 7
A cor azul-marinho é escrita como 12 0A 8F no sistema tripleto
hexadecimal.
Portanto, cada dupla terá 16 possibilidades para a primeira posição
e mais 16 para a segunda, formando um byte de 256 possibilidades.
Como temos três duplas, as possibilidades de combinação serão 256 ·
256 · 256 = 16.777.216.
Essa estrutura de cores é usada para documentos HTML, CSS, entre
outros.
É possível observar os códigos hexadecimais de uma quantidade
considerável de cores e a conversão para outros sistemas de cores que
podem ser adotados computacionalmente.
A seguir, veremos o processo da transformação inversa, ou seja, co-
nhecendo um número na base 10, converteremos ele para a base b
desejada.
2.2.4 Processo inverso
Nesta seção trabalharemos com a conversão de números na base
decimal (x)10, os quais serão convertidos para uma base b qualquer.
Ou seja, queremos trabalhar com a seguinte representação algébrica:
(x)10 = (dndn–1 ... d0, d–1 ...)b
(x)10 = dn · b
n + dn–1 · b
n–1 + … + d0 · b
0 + d–1 · b
–1 + …
Inicialmente, para conseguirmos realizar a conversão, separamos
a parte inteira de (x)10 da sua parte fracionária (também chamada de
mantissa), obtendo (x)10 = x
i + xf. Assim, temos
xi = dn · b
n + dn–1 · b
n–1 + … + d0 · b
0
x
d
b
d
b
f � � ��� �1
1
2
2
Uma tabela bem extensa
de combinações de cores
pode ser encontrada no
site Nas artes gráficas.
Disponível em: http://
nasartesgraficas.blogspot.
com/2014/08/lista-de-cores.html.
Acesso em: 2 jun. 2021.
Site
http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html
http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html
http://nasartesgraficas.blogspot.com/2014/08/lista-de-cores.html
Noções sobre sistemas de numeração 41
Portanto,precisamos determinar os valores para o conjunto
{dn, dn–1, ...}, que é composto tanto de elementos da parte inteira como
de elementos da parte fracionária.
• Parte inteira
(xi = dn · b
n + dn–1· b
n–1 + … + d0 · b
0) ÷ (b) =
x
b
d b d b d
d
b
i
n
n
n
n� � � � ��� �� �
�1
1
2
1
0
Observe que d0 é o resto da divisão de x
i por b, pois d1 + d2 ∙ b1 + ...
+ dn–1 · b
n–2 + dn ∙ bn–1 é inteiro e
d
b
0 é uma fração com d0 < b. Da mesma
forma, o resto da divisão de d1 + d2 ∙ b1 + ... + dn–1 · bn–2 + dn ∙ bn–1 por b
é d1. Ou seja, repetindo esse processo encontramos os algarismos d0,
d1, d2, ..., dn.
Para a análise da parte inteira, temos uma ferramenta extremamen-
te simples que pode ser usada: a divisão.
Por meio de sucessivas divisões, podemos rapidamente converter
um número da base decimal para a base binária.
Exemρlo 8
Para a conversão de (3)10 para a base binária, fazemos:
3 ÷ 2 = 1 → Resto 1
1 ÷ 2 = 0 → Resto 1
O resultado será obtido, justamente, por meio dos restos. Portanto,
(3)10 = (11)2.
Também podemos converter um número na base 10 para a base
binária por meio das divisões sucessivas, como é feito no exemplo
a seguir.
42 Matemática para Computação
Exemρlo 9
A conversão do número (142)10 para a base binária poderia ser re-
solvida assim:
(142)10 = (10001110)2
142 2
71 2
35 2
17 2
8 2
4 2
2 2
1 2
0
0
0
0
0
1
1
1
1
Por fim, um exemplo da conversão de bases de um número decimal.
Exemρlo 10
Vamos converter o número 3,625 para a base binária (b = 2). Pri-
meiramente, decompomos 3,625 na soma de suas partes inteira e
fracionária.
x = 3 + 0,625
Logo, xi = 3 e xf = 0,625.
Nesse exemplo, resolveremos a parte inteira dessa conversão. Assim,
precisamos fazer sucessivas divisões por b = 2. Então:
xi = 3 = 1 · 2 + 1 = 1 · 21 + 1 · 20
Portanto, xi = 1 · 21 + 1 · 20 = (11)2.
Para a parte fracionária do número, temos o seguinte:
• Parte fracionária
x
d
b
d
b
b b x d
d
b
f f� � ��
�
�
�
�
�
� � � � � � � � ��� � � �11 22 1 2
Noções sobre sistemas de numeração 43
Nesse produto, note que a parte inteira é d–1 e a parte fracionária
é
d
b
�� ��2 ; ao multiplicarmos novamente por b, temos d–2. Para encon-
trar os algarismos restantes, repetimos esse processo.
Exemρlo 11
Continuando o Exemplo 10, agora precisamos fazer sucessivas
multiplicações por b = 2, para obtermos a parte fracionária do nú-
mero 3,625.
xf = 0,625
2 · xf = 1,25 · 2–1 = 1 · 2–1 + 0,25 · 2–1
= 1 · 2–1 + (0,5 · 2–1) · 2–1 = 1 · 2–1 + 0,5 · 2–2
= 1 · 2–1 + (1 · 2–1) · 2–2 = 1 · 2–1 + 1 · 2–3
Portanto, xf = 1 · 2–1 + 0 · 2–2 + 1 · 2–3 = (101)2.
Logo, (3,625)10 = (11,101)2.
Outras ferramentas computacionais podem ser usadas – entre elas,
encontram-se algumas linguagens de programação, como Sclilab e
PythonTM.
Aqui, relembramos que o processo aplicado pelo computador é o
de converter de binário para decimal, mas as conversões são impor-
tantes para garantir a veracidade dos nossos cálculos e a viabilidade de
possíveis aplicações.
2.3 Representação em ponto flutuante
Vídeo Um número, na matemática, pode ser infinito, e isso é impossível
de ser representado no computador, visto que este trabalha com um
número de bits limitado e predefinido (WEBER, 2004).
Pensando na estrutura numérica computacional, dizemos que há
três formas possíveis de representação de um número no computador:
I. Inteiro natural.
II. Inteiro relativo.
III. Generalização dos dois casos anteriores, ou seja, um número real.
44 Matemática para Computação
É possível representar números inteiros, ou seja, considerar a
parte negativa do conjunto, atribuindo um bit mais à esquerda, cha-
mado de sinal ou bit forte. Por meio desse primeiro bit saberemos se
o número é positivo ou negativo.
Já no caso dos números reais, ou seja, considerando também núme-
ros decimais, a Institute of Electrical and Electronic Engineers (IEEE) defi-
ne uma fórmula para ser aplicada (padrão IEEE754). Essa representação
(Quadro 1) é chamada de representação em ponto flutuante. Seja um com-
putador de 32 bits, essa estrutura fica escrita da seguinte forma:
(–1)S ∙ bE ∙ F
Quadro 1
Organização do ponto flutuante
S
bit1�
E F
Fonte: Elaborado pela autora.
Em que:
• b é a base;
• S = 0 (número positivo) ou S = 1 (número negativo);
• E deve ser calculado por m ≤ E ≤ M, com m sendo o valor míni-
mo que a máquina pode representar e M sendo o valor máximo
(|m| ≈ M);
• F, chamado de mantissa, conterá os bits situados após a vírgula.
Acompanhe o exemplo a seguir para compreender melhor.
Exemρlo 12
Considere uma máquina com registro de 32 bits e base b = 2. Pelo
padrão IEEE754 (Quadro 2), 1 bit será usado para o sinal (S), 8 bits serão
usados para o expoente (c7, ..., c0) e 23 bits serão usados para a man-
tissa (d1, ..., d23).
Quadro 2
Padrão IEEE754
S c7 c6 ... c0 d1 d2 ... d22 d23
Fonte: Elaborado pela autora.
Se você se interessou por
esse tema, sugerimos a
leitura do material Padrão
IEEE 754 para aritmética
binária de ponto flutuante.
Disponível em: https://www.lia.ufc.
br/~valdisio/download/ieee.pdf.
Acesso em: 2 jun. 2021.
Leitura
https://www.lia.ufc.br/~valdisio/download/ieee.pdf
https://www.lia.ufc.br/~valdisio/download/ieee.pdf
Noções sobre sistemas de numeração 45
Assumindo que E = c – BIAS, em que BIAS é o valor do deslocamento
do expoente (polarização), temos:
x = (–1)S ∙ 2c–BIAS F
com
c = (c7c6 ... c0)2 e F = (1,d1d2 ... d22d23)
De acordo com Gilat e Subramaniam (2008, p. 23, grifos do original),
“computadores armazenam números e realizam cálculos em precisão
simples ou em precisão dupla. Na precisão simples, os números são
armazenados em uma cadeia de 32 bits (4 bytes), e, na precisão dupla,
em uma cadeia de 64 bits (8 bytes)”.
Exemρlo 13
Queremos representar em notação ponto flutuante os números
• x = (1)10
• y = (–11)10
• z = (231)10
assumindo precisão simples (32 bits) e base hexadecimal.
No primeiro caso, x = (1)10, teremos a primeira casa composta do
sinal, logo S = 0, pois 1 é positivo. Assim:
0 0 1 0 0 0 0 0 0
Agora, no segundo caso, y = (–11)10, como o valor é negativo, a pri-
meira casa será representada por S = 1. Assim:
1 b 0 0 0 0 0 0 0
No último caso, ou seja, z = (231)10, teremos S = 0 e a representação:
0 e 7 0 0 0 0 0 0
Note que na representação em ponto flutuante dos três números
não usamos as casas referentes a:
d1 d2 ... d22 d23
Isso porque em nenhum deles há parte fracionária.
46 Matemática para Computação
Note que aumentar o número de bits na mantissa melhora a preci-
são. Já aumentar a quantidade de bits no expoente permite que tenha-
mos um intervalo de números representáveis muito maior. Com isso,
é possível perceber padrões muito bem definidos para a construção do
cálculo numérico e da matemática computacional.
2.4 Erros numéricos
Vídeo Quando falamos de erros, estamos tratando da diferença entre o
valor real e o valor obtido.
É comum que sejam necessárias diversas simplificações do pro-
blema real para que se tenha um modelo matemático com solução
possível.
Observe a Figura 6 a seguir, que apresenta a comparação entre um
modelo físico (geoide) e um modelo matemático (elipsoide) da super-
fície da Terra.
Figura 6
Comparação entre modelos
Modelo físico – geoide
jd
rv
_a
rt/
Sh
ut
er
st
oc
k
Modelo matemático – elipsoide
Al
ex
an
de
rZ
am
/S
hu
te
rs
to
ck
Assim sendo, o processo de propagação de erros começa quan-
do transformamos um problema real em um modelo físico e este
em um modelo matemático. Tal modelo matemático poderá ser
resolvido de modo que tenhamos uma solução analítica ou uma
solução numérica.
Noções sobre sistemas de numeração 47
Ku
bk
o/
Sh
ut
te
rs
to
ck
Problema
real
Modelo
físico
Modelo
matemático
Solução
analítica
Solução
numérica
Implementação
computacional
Resultado
numérico
Note que ao desenvolvermos o modelo matemático, precisamos
escolher entre a obtenção de uma solução analítica e uma solução
numérica.
Neste ponto, temos um grandequestionamento. Por que usar um método
numérico?
A resposta é mais simples do que imaginamos. Os modelos que
possuem solução analítica precisam ser extremamente simplificados.
Já os modelos que podem ser resolvidos numericamente podem con-
48 Matemática para Computação
ter mais variáveis e equações e, assim, um requinte maior nas equa-
ções que os contemplam.
Como o modelo usado para a obtenção numérica é mais “refinado”, o
erro inerente ao método e à máquina pode ser muito menor se compa-
rado ao erro obtido com a solução analítica, que foi encontrada por meio
de um modelo muito mais “grosseiro”.
Com isso, concluímos que nem sempre usamos o mesmo modelo
matemático para as duas abordagens. Em geral, modelos matemáticos
computacionais podem abranger um número maior de situações quan-
do comparados ao problema real.
Por meio do arredondamento e do truncamento, que especificare-
mos na sequência, conseguimos perceber a propagação de erros a que
a resolução de um problema pode estar exposta.
Como vimos, os números não são representados computacionalmen-
te de maneira exata. Essa “perda” dependerá da capacidade da máquina.
A precisão, denotada por p, de um computador é o número de dígi-
tos significativos usados para representar um número. Os dígitos signi-
ficativos são todos os dígitos certos adicionados ao primeiro algarismo
duvidoso.
Dessa forma, os números infinitos (ou mesmo muito grandes) aca-
bam sendo arredondados ou truncados, ocasionando erros. Esses
mesmos números, quando em operações, ocasionarão a chamada pro-
pagação de erros.
Além desses erros, ainda temos a chamada incerteza dos dados e
os erros de modelagem matemática. Nesse caso, em vez de pensar na
transformação de um número para sua forma finita, levamos em con-
sideração a construção do modelo matemático e, com isso, a acurácia
dos instrumentos de medição que estão envolvidos na construção desse
modelo, além das ferramentas matemáticas disponíveis para solucionar
o problema.
Vamos entender qual tipo de ajuste é necessário quando arredon-
damos ou truncamos um número e o que isso acarreta para o cálculo.
2.4.1 Erro de arredondamento
O arredondamento de um número é feito analisando o primeiro al-
garismo após o dígito duvidoso.
acurácia: “[Física] Proxi-
midade entre o resultado
de um instrumento de
medida e o verdadeiro
valor do que foi medido”
(DICIO, 2021).
Glossário
Noções sobre sistemas de numeração 49
Caso o dígito duvidoso seja maior do que 5, aumenta-se de uma unidade
o algarismo duvidoso e desprezam-se os demais.
Caso o dígito duvidoso seja menor do que 5, mantém-se o valor do
algarismo duvidoso e desprezam-se os demais.
Caso o dígito duvidoso seja igual a 5, há dois caminhos:
• Se o algarismo duvidoso imediatamente anterior à parte despre-
zada for um número ímpar, deve-se aumentá-lo em uma unidade.
• Se o algarismo duvidoso imediatamente anterior à parte despre-
zada for um número par, deve-se deixá-lo como está (inalterado).
di
fu
gi
c
re
at
ive
/S
hu
tte
rs
to
ck
Para compreender essas especificações sobre arredondamento,
acompanhe o exemplo a seguir.
Exemρlo 14
1
3
0 333 0 33� � �� � �, � ,
π = 3,1415926 ... ≈ 3,141693
1,55500... ≈ 1,56
0,805... ≈ 0,80
Adotamos o arredondamento numérico porque computacional-
mente não é possível representar números infinitos, ou seja, esse tipo
de ajuste é feito por causa das limitações existentes na representação
numérica em máquinas digitais. Mas existem outros tipos de erros que
podem se propagar quando transformamos um problema.
2.4.2 Erro de truncamento
O chamado truncamento será o corte aplicado aos dígitos não sig-
nificativos de um número infinito (ou muito grande), de acordo com a
precisão possível da máquina.
50 Matemática para Computação
O truncamento também ocorre quando se aplica um método numé-
rico na solução de um problema e esse método leva a uma sucessão de
termos infinitos. Computacionalmente, essa abordagem não é possível;
nesses casos, trunca-se a série de termos em determinado ponto no
qual o erro seja aceitável.
Em geral, é necessário definir em cada problema o que é conside-
rado um erro aceitável. Assim, o resultado encontrado, após o trunca-
mento, será analisado perante a obtenção desse erro.
Resumidamente, um erro de truncamento ocorre quando transfor-
mamos uma representação de um processo infinito em uma represen-
tação finita.
É comum, por exemplo, truncarmos séries de funções, como no
exemplo a seguir.
Exemρlo 15
Seja a função sen x escrita por meio de uma série de potências na forma:
sen x x x x x� � � � ��
3 5 7
3 5 7! ! !
Sabemos que o valor de sen �π
6
é igual a 1
2
. Contudo, se calcular-
mos esse valor por meio de uma série de potências trigonométrica
truncadas, teremos:
sen � �
� � �
6 6
6
3 2 1
6
5 4 3 2 1
6
7 6 5
3 5 7
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
� � � �
�
�
�
�
�
�
�
� � �44 3 2 1� � �
Nesse caso, sen
�
6
0 49999999187�
�
�
�
�
� � , .
Note que para esse cálculo, além do erro de truncamento, ainda te-
mos um erro de arredondamento. Portanto, começamos a perceber a
propagação de erros intrínseca em diversos métodos computacionais.
2.4.3 Erro absoluto e erro relativo
Com os ajustes numéricos necessários para a representação com-
putacional (arredondamento, truncamento etc.), além dos ajustes nos
Noções sobre sistemas de numeração 51
modelos e nas demais aproximações aplicadas, surge a questão refe-
rente à quantificação dos erros envolvidos nesses processos.
Para verificar se o resultado atingido foi bom, é necessário compará-
-lo ao resultado exato.
Nesse ponto, surgem algumas métricas que nos permitem quanti-
ficar os erros.
As medidas de erro mais utilizadas são o erro absoluto e o erro relativo.
Definição 2 – erro absoluto
Sejam x um número real e�x sua aproximação. O erro absoluto da aproximação
�x é definido, de acordo com Justo et al. (2021), como:
E x xA � �
Apresentamos a seguir um exemplo que nos auxilia na compreen-
são do cálculo para esse tipo de erro.
Exemρlo 16
A área da circunferência é dada por A = πr². Se r = 3, então a área
exata será dada por A = 9π. Mas o que ocorre se π for arredondado?
Sejam π1 = 3,14 e π2 = 3,141593. Então, A1 = 9 · 3,14 = 28,26 e A2 =
9 · 3,141593 = 28,274337.
Erro absoluto: E x xA � � → EA = |28,274337 – 28,26| = 0,014337.
Em muitos casos, desejamos calcular uma taxa entre o erro e a solu-
ção real. Nessa situação, precisamos do chamado erro relativo, definido
a seguir.
Definição 3 – erro relativo
Sejam x um número real e�x sua aproximação. O erro relativo da aproximação
�x é definido, de acordo com Justo et al. (2021), como:
E
x x
x
�xR �
�
�, 0
O erro relativo é adimensional e, muitas vezes, é expresso em
porcentagens.
52 Matemática para Computação
Exemρlo 17
Utilizando os mesmos dados do Exemplo 14, vamos calcular o erro
relativo.
Sejam π1 = 3,14 e π2 = 3,141593. Então, A1 = 9 · 3,14 = 28,26 e A2 =
9 · 3,141593 = 28,274337.
Erro relativo: E
x� �x
xR
�
�
.
E
� �
� � %R �
�
� � �
28 274337 28 26
28 274337
0 0005070675927 100 0 050
, ,
,
, , 77%
Uma forma de minimizar o alastramento de erros em um modelo
numérico é reduzir o número de operações.
Exemρlo 18
Considere o polinômio dado por:
pn(x) = anx
n + an–1x
n–1 + … + a1x
1 + a0 = ((…(anx + an–1)x + an–2)x + …a1)x + a0
Note que a primeira representação do polinômio contém mais ope-
rações do que a segunda representação.
Sendo assim, o erro geral no segundo caso será menor, pois serão
necessários menos ajustes numéricos e, com isso, um menor alastra-
mento de erros.
Esse tipo de manipulação precisa ser trabalhado com suas especifi-
cidades, dentro de cada método numérico e cada situação que permita
a implementação computacional.
CONSIDERAÇÕES FINAIS
Neste capítulo percorremos trechos da história da matemática que
permitiram o desenvolvimento da história da computação.
Identificamos alguns matemáticos que estiveram diretamente relacionados
com a construçãonão só das linguagens de programação, mas da própria má-
quina digital eletrônica (computador moderno) e do modo como ela opera.
• O relato de alguns
acidentes atribuídos a
erros de cálculo numérico
pode ser encontrado na
leitura de Some disasters
attributable to bad
numerical computing.
Apesar de o texto estar
em língua estrangeira,
ele pode ser facilmente
traduzido por meio de
um tradutor on-line.
Disponível em: http://www-
users.math.umn.edu/~arnold//
disasters/. Acesso em: 2 jun. 2021.
• Além disso, indicamos
também a leitura de Erros
de cálculo na engenharia.
Disponível em: https://www.
aedb.br/seget/arquivos/
artigos18/23226187.pdf. Acesso
em: 2 jun. 2021.
Leitura
http://www-users.math.umn.edu/~arnold//disasters/
http://www-users.math.umn.edu/~arnold//disasters/
http://www-users.math.umn.edu/~arnold//disasters/
https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf
https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf
https://www.aedb.br/seget/arquivos/artigos18/23226187.pdf
Noções sobre sistemas de numeração 53
Percebemos a importância das estruturas lógicas-matemáticas en-
volvidas no processo por trás da lógica computacional e, com isso, re-
pensamos algumas das estruturas matemáticas clássicas que, quando
convertidas para serem interpretadas pelo computador, ainda mantêm
suas caraterísticas principais, ou seja, mantêm sua estrutura matemática.
Com base em todos esses conceitos, reforçamos a importância do es-
tudo da matemática para todos interessados pela área da computação,
com todas as suas ramificações e possibilidades.
ATIVIDADES
Podemos considerar o sistema de numeração romano um sistema
aditivo ou um sistema posicional? Explique.
Atividade 1
É possível converter um número na base 10 para a base hexadecimal
por meio de divisões sucessivas? Explique essa conversão e converta o
número (9)10 para essa base.
Atividade 2
Considere a escrita do número de Napier da forma e = 2,718... e
e
n
n
� � � � � ��
�
�
0
1 1
0
1
1
1
2
1
3
�
! ! ! ! !
No primeiro caso, devemos usar qual tipo de ajuste numérico para obter
um número finito? E no segundo caso? Quais são os erros envolvidos
em cada um dos casos?
Atividade 3
REFERÊNCIAS
ALMEIDA, M. C. Origens da matemática: a pré-história da matemática – o neolítico e o
alvorecer da história. Curitiba: Progressiva, 2011. (v. 1)
CARROLL, L. Aventuras de Alice no país das maravilhas & Através do espelho e o que Alice
encontrou por lá. São Paulo: Zahar, 2013.
DICIO. Dicionário Online de Português. 2021. Disponível em: https://www.dicio.com.br/.
Acesso em: 2 jun. 2021.
GILAT, A.; SUBRAMANIAM, V. Métodos numéricos para engenheiros e cientistas: uma
introdução com aplicações usando o MATLAB. Porto Alegre: Bookman, 2008.
JUSTO, D. A. R. et al. REAMAT: cálculo numérico. Porto Alegre: UFRGS. Disponível em: https://
www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html. Acesso em: 2 jun. 2021.
SAMPEDRO, J. Um sistema binário inventado na Polinésia séculos antes de Leibniz.
El País, 16 dez. 2013. Disponível em: https://brasil.elpais.com/brasil/2013/12/16/
sociedad/1387215405_275511.html. Acesso em: 2 jun. 2021.
WEBER, R. F. Fundamentos de arquitetura de computadores. v. 8. Porto Alegre: Bookman, 2004.
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/main.html
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
https://brasil.elpais.com/brasil/2013/12/16/sociedad/1387215405_275511.html
54 Matemática para Computação
3
Matrizes
Quando falamos em matemática para computação, temos como
objetivo possibilitar uma base para conceitos que serão usados não
só como ferramenta para desenvolver e aprimorar o raciocínio lógico
dentro da matemática e de outras disciplinas, mas também como ins-
trumento essencial para a programação – seja esta como objeto de
aprendizagem teórico ou mesmo como objeto aplicado.
Você já se perguntou quanta matemática está por trás de um sim-
ples software de reconhecimento de imagem? Ou como transformar
um problema real em um problema computacional? É a matemática
envolvida nessas situações que queremos apresentar.
Assim, iniciamos com o conceito de matriz, possivelmente já visto
por muitos de vocês no ensino médio, mas que será reforçado, nesse
momento, para que possamos ampliar o nosso ferramental aplicado
à computação.
Dessa forma, este capítulo trará a estrutura das matrizes e as suas
propriedades, pois queremos possibilitar o entendimento da relação
desse conceito com estruturas vetoriais, listas, arrays, dentre outros,
que são essenciais na maior parte das linguagens de programação.
Na sequência, aprofundaremos a definição de operação matricial,
abordando determinantes, matrizes inversas e fatoração de matrizes.
Essa base auxiliará no entendimento de construções da lógica da pro-
gramação e na aplicação dessa lógica voltada ao tratamento vetorial,
ao processamento numérico e à modelagem computacional.
A ideia é possibilitar um estudo crítico e de real aprendizado,
direcionado para as necessidades da profissão e do mundo que
nos cerca.
Matrizes 55
Com o estudo deste capítulo, você será capaz de:
• relacionar o conceito de vetor e matriz;
• pensar a definição de multiplicação matricial de
modo computacional;
• compreender o conceito de base de espaços formados por
vetores, para a agilidade dos resultados computacionais;
• entender e aplicar o processo de fatoração matricial, conhe-
cido por método de Gauss;
• aplicar o conceito de algoritmo para resolver os processos
de fatoração e decomposição matriciais;
• interpretar a inversa de uma matriz por meio de processos
de decomposição matricial.
Objetivos de aprendizagem
3.1 Vetores de uma matriz
Vídeo Você conhece as regras do jogo de xadrez? Antes de entender qual-
quer regra que envolva esse tipo de jogo, precisamos conhecer o tabu-
leiro, pois toda e qualquer regra estará vinculada à posição em que as
peças se encontram.
Assim, o tabuleiro de xadrez é formado por linhas, representadas
por números, e colunas, retratadas por letras, conforme podemos
observar na Figura 1.
Figura 1
Linhas e
colunas no
xadrez Va
pa
rt/
Sh
ut
te
rs
to
ck
56 Matemática para Computação
Assim, quando o jogador pensa na movimentação que fará com sua
peça, ele identifica a linha e a coluna para onde fará o movimento.
Por exemplo, o peão branco na casa 2D pode se movimentar para a
4D. Outro peão branco, localizado na casa 2C, pode avançar para a 4C.
Na Figura 2, temos o peão preto, que foi movido para a casa 5D.
Dimitrios Karamitros/Shutterstock
Figura 2
Movimentação
no tabuleiro
de xadrez
Note que compreender a movimentação por meio de linhas e
colunas 1 facilita muito a escrita de jogadas. Se isso não fosse normali-
zado dessa forma, seria bem difícil explicar diferentes jogadas e movi-
mentações para outros jogadores por intermédio de obras literárias e
artigos técnicos.
Partindo dessa ideia, definimos matematicamente o conceito de matriz.
Definição 1
Chama-se matriz de ordem m por n a um quadro de m ⨯ n elementos dispostos
em m linhas e n colunas da seguinte forma (LEON, 2019):
A
a a a
a a a
a a a
am n
n
n
m m mn
ij m� �
��
�
�
�
�
�
�
�
�
�
�
�
�
11 12 1
21 22 2
1 2
�
� � � �
�
[ ] ��n
Se pensarmos em matriz como uma forma de organizar coisas em
posições específicas, é possível perceber que os elementos dessa ma-
triz podem ser qualquer objeto. Contudo, matematicamente, entende-
mos os elementos de uma matriz como números (reais ou complexos),
funções ou, ainda, outras matrizes.
Ficou curioso com as
movimentações possíveis
do jogo de xadrez? Suge-
rimos a leitura de duas
obras que podem ajudá-lo
nessa área e, como
consequência, no entendi-
mento das matrizes:
SUMMERSCALE, C. Xadrez: guia
passo a passo totalmente ilustrado.
São Paulo: Zastras, 2008.
NIMZOWITSCH, A. Meu sistema: o
primeiro livro de ensino de xadrez.
São Paulo: Solis, 2007.
LeituraEstamos usando a
nomenclatura usual para
matrizes (linha e coluna),
mas, no xadrez, o padrão
é nomear primeiro a colu-
na e depois a linha.
1
https://www.amazon.com.br/Xadrez-Guia-Passo-Totalmente-Ilustrado/dp/8521313993/ref=sr_1_2?__mk_pt_BR=%C3%85M%C3%85%C5%BD%C3%95%C3%91&dchild=1&keywords=xadrez+para+ilustrado&qid=1623522307&s=books&sr=1-2
https://www.amazon.com.br/Xadrez-Guia-Passo-Totalmente-Ilustrado/dp/8521313993/ref=sr_1_2?__mk_pt_BR=%C3%85M%C3%85%C5%BD%C3%95%C3%91&dchild=1&keywords=xadrez+para+ilustrado&qid=1623522307&s=books&sr=1-2
Matrizes 57
A nomenclatura usual para uma matriz é dada por:
Ol
lie
T
he
D
es
ig
ne
r/
Sh
ut
te
rs
to
ck
Letras maiúsculas para
simbolizar matrizes.
Letras minúsculas para
denotar seus elementos.
A posição de cada elemento
é apresentada por meio de
subíndices, sendo que usamos
i para a posição do elemento
em relação à linha e j para
a posição do elemento em
relação à coluna aij.
Para indicar a ordem de
uma matriz A (isto é, o
número de linhas e colunas),
escreve-se Am⨯n, sendo que
m representa o número de
linhas, e n o de colunas.
Cada elemento da matriz A tem dois índices: aij, sendo que o primei-
ro índice representa a linha a que esse elemento pertence, e o segundo
a coluna. Dessa forma, [aij], com i variando de 1 a m, e j de 1 a n, repre-
sentamos abreviadamente a matriz A de ordem m por n.
Ol
lie
T
he
D
es
ig
ne
r/
Sh
ut
te
rs
to
ck
Duas matrizes A = [aij] e
B = [bij] de ordem m por n
são iguais (equivalentes) se, e
somente se, aij = bij. A matriz de ordem n por 1 é
uma matriz coluna:
A
a
a
a
an
n
ij n� ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�1
11
21
1
1
[ ]
A matriz de ordem 1 por n é
uma matriz linha:
A a a a an n ij n1 11 12 1 1� �� ��� �� � [ ]
58 Matemática para Computação
Cada linha (ou coluna) representa um vetor. Assim, se a matriz é de
ordem m por n, teremos vetores m, vetores linha ou n vetores coluna.
Logo, o que determina se olharemos para as linhas ou para as colu-
nas como vetores é a aplicação relacionada a essa matriz.
De acordo com Feofiloff (2018):
um vetor, ou arranjo (= array), é uma estrutura de dados que
armazena uma sequência de objetos, todos do mesmo tipo,
em posições consecutivas da memória RAM (= random access
memory) do computador. Essa estrutura permite acesso aleató-
rio: qualquer elemento do vetor pode ser alcançado diretamen-
te, sem passar pelos elementos anteriores (o décimo elemento,
por exemplo, pode ser alcançado sem que seja necessário passar
antes pelo primeiro, segundo, etc., nonos elementos).
Note que Feofiloff (2018) usa termos específicos da computação,
mas que são, simplesmente, conceitos matemáticos que já conhece-
mos: vetores e matrizes.
Um array pode ser unidimensional ou multidimensional. Quando o
array é unidimensional, temos o vetor, que é capaz de armazenar mui-
tas variáveis do mesmo tipo. Uma coleção de arrays, ou seja, um array
multidimensional, é entendida como uma matriz; também pode ser
compreendida como um vetor de vetores.
Cada elemento da matriz é acessado pelos seus índices, ou seja, i e j,
que determinam a posição desse elemento.
A proposta do nosso material não é a de simplesmente revisar o
conceito de matriz, mas a de trazer uma nova abordagem para este,
pensando na sua aplicação na computação. Para isso, vamos focar as
maneiras de aplicarmos as matrizes e os seus vetores, tendo como
objetivo as operações realizadas computacionalmente.
É nesse contexto que entramos na próxima seção, na qual aborda-
remos as operações matriciais e os algoritmos.
3.2 Análise do algoritmo padrão para
multiplicação de matrizes Vídeo
Talvez você já tenha pensado no processo de adição e subtração
matricial de maneira computacional. A soma e a subtração entre duas
Matrizes 59
matrizes exigem apenas que a ordem destas seja igual, visto que, para
a obtenção do resultado, será necessário somar ou subtrair, respecti-
vamente, termo a termo dessas matrizes.
A soma de duas matrizes A = [aij] e B = [bij] de ordem m por n é uma
matriz C = [cij], tal que cij = aij + bij.
a a
a a
b b
b b
an
n mn
n
n mn
11 1
1
11 1
1
1�
� � �
�
�
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11 11 1 1
1 1
� �
� �
�
�
�
�
�
�
�
�
�
�
b a b
a b a b
n n
n n mn mn
�
� � �
�
Para compreender essa operação, acompanhe o exemplo a seguir.
Exemρlo 1
Sejam as matrizes A �e�B ��
�
�
�
�
�
� �
�
�
�
�
�
�
1 2
3 4
4 5
6 7
, então:
A B� �
� �
� �
�
�
�
�
�
� �
�
�
�
�
�
�
1 4 2 5
3 6 4 7
5 7
9 11
A mesma propriedade é válida para a subtração entre matrizes,
como podemos notar no exemplo a seguir.
Exemρlo 2
Sejam as matrizes A �e�B�
�
�
�
�
�
� �
�
�
�
�
�
�
1 2
3 4
4 5
6 7
, então:
A B� �
� �
� �
�
�
�
�
�
� �
� �
� �
�
�
�
�
�
�
1 4 2 5
3 6 4 7
3 3
3 3
Contudo, o processo de multiplicação não é tão intuitivo. Por
esse motivo, apresentamos, na sequência, o algoritmo que permite
fazermos multiplicações entre duas matrizes.
60 Matemática para Computação
Algoritmo 1
Sejam A = [aij]m⨯n e B = [brs]n⨯p, o produto de A por B é definido como
AB = [cuv]m⨯p
onde
c a b a b a buv
k
n
uk kv u v un nv� � ���
�
�
1
1 1
O produto entre duas matrizes Am⨯n e Bl⨯p só é possível se o número
de colunas da matriz A for igual ao número de linhas da matriz B, n = l.
O resultado desse produto será uma matriz de ordem m ⨯ p.
O elemento resultante desse produto será denotado por cij (i-ésima
linha e j-ésima coluna da matriz produto) e obtido por meio da soma en-
tre os produtos dos elementos da i–ésima linha da primeira matriz pelos
elementos correspondentes da j–ésima coluna da segunda matriz.
Acompanhe o exemplo a seguir para compreender melhor como
calculamos a multiplicação de matrizes.
Exemρlo 3
Vamos efetuar o produto entre as matrizes A1⨯2 = [–1 1] e
B2 3
2 1 4
3 4 3�
�
� �
�
�
�
�
�
�
� .
Verificamos se o número de colunas da matriz A é igual ao número
de linhas da matriz B. Nesse caso:
colunas de A = linhas de B = 2
Portanto, o produto entre matrizes é possível e dará origem a uma
matriz C, com o número de linhas de A e o número de colunas de B, ou
seja, originará uma matriz C1⨯3.
C1 3 1 1
2 1 4
3 4 3�
� ��� �� �
� �
�
�
�
�
�
�
�
= [(–1) · 2 + 1 · 3 (–1)(–1) + 1 · 4 (–1)(–4) + 1 · (–3)]
= [1 5 1]
m
yd
eg
ag
e/
Sh
ut
te
rs
to
ck
Matrizes 61
A multiplicação de matrizes tem as seguintes propriedades:
• Em geral, AB ≠ BA.
• AB = 0, sem que A = 0 ou B = 0.
• AI = IA = A, onde I é a matriz identidade.
• Distributividade:
• A(B + C) = AB + AC;
• (A + B)C = AC + BC;
• (AB)C = A(BC).
• A(AB)t = BtAt.
• 0A = 0 e A0 = 0.
Fechamos esta seção com as propriedades algébricas da multipli-
cação entre matrizes. Com isso, temos em mãos as propriedades ma-
triciais necessárias para resolvermos diversos exemplos e aplicações.
3.3 Bases
Vídeo Vimos que uma matriz é constituída de linhas e colunas. Essas
mesmas linhas e colunas podem ser consideradas vetores dessa matriz.
Observe a Figura 3, que apresenta, graficamente, duas equações
de retas, representadas em um mesmo sistema de coordenadas
cartesianas, ℝ².
Figura 3
Sistema de equação
2 4
3 2
x y
x y
� �
� �
�
�
�
3,5
4
3,5 4,5 5,5–3,5 –3 –2,5 –2 –1,5 –1 –0,5 0
3
3 4 5 6
X
Y
2,5
2,5
2
2
1,5
1,5
1
1
–1
0,5
0,5
0,5
eq2: 3x – y = 2eq1: 2x + y = 4
eq1
eq2
Fonte: Elaborada pela autora.
62 Matemática para Computação
Esse sistema, escrito como
2 4
3 2
x y
x y
� �
� �
�
�
�
��
, pode ser representado na
forma matricial a seguir:
2 1
3 1
4
2�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
x
y
Ao analisarmos os vetores linha da matriz dos coeficientes, dados
por v1 = [2, 1] e v2 = [3, –1], podemos expressar que v1 não pode ser
escrito como uma combinação linear de v2, ou seja, não podemos de-
notar como v1 ≠ αv2.
Essa simples análise nos fornece a informação de que esses veto-
res são linearmente independentese, como eles são formados por
duas coordenadas, isto é, são bidimensionais e estão contidos em um
espaço bidimensional, ainda podemos afirmar que esses mesmos dois
vetores, v1 e v2, formam uma base para o ℝ2.
No caso de um sistema de equações composto por n equações e
n variáveis, identificar que os vetores que formam a matriz dos coefi-
cientes são, também, uma base para ℝn nos permite afirmar que esse
sistema é compatível e determinado, então tem uma única solução.
Assim, para identificar se n vetores de uma matriz formam uma
base para o espaço ℝn, precisamos analisar duas situações:
I. se os vetores são linearmente independentes (LI);
II. se os vetores geram ℝn.
A base mais simples para um espaço de vetores é a base canôni-
ca. Para o ℝ², ela é formada pelos vetores e1 = (1, 0) e e2 = (0, 1). Note
que, se admitirmos um outro vetor qualquer nesse sistema, por exem-
plo, o vetor v = (–5, 3), este será escrito como uma combinação linear
(Figura 4) de e1 e e2 na forma:
(–5, 3) = –5(1, 0) + 3(0, 1) = –5v1 + 3v2
Geometricamente, o que estamos mostrando é que existem escala-
res α1 = –5 e α2 = 3, tais que v = α1 v1 + α2 v2.
Trouxemos o conceito
de base pensando na
proposta aplicada, mas,
caso você tenha interesse
em se aprofundar nesse
tema, com a visão da
álgebra linear, sugerimos
o vídeo Combinações li-
neares, subespaços gerados
e bases | A essência da
Álgebra Linear, capítulo
2, publicado pelo canal
3Bluw1Brown.
Disponível em https://www.youtu-
be.com/watch?v=k7RM-ot2NWY.
Acesso em: 6 jul. 2021.
Vídeo
https://www.youtube.com/watch?v=k7RM-ot2NWY
https://www.youtube.com/watch?v=k7RM-ot2NWY
Matrizes 63
Figura 4
Combinação linear entre v1 e v2 y
x
3v2
v2 = (0, 1)
v1 = (1, 0)
–5v1
Fonte: Elaborada pela autora.
Portanto, uma combinação linear pode ser definida como:
Definição 2
Sejam v1, ..., vn elementos de um espaço de vetores V, então v é uma combinação
linear de v1, ..., vn se existirem números reais α1, ... ,αn, tais que:
v = α1v1 + ... + αnvn (1)
Já o que define a independência linear é:
Definição 3
Uma sequência de vetores v1, ..., vn de um espaço vetorial V é linearmente
independente (LI) se:
α1v1 + ... + αnvn =
0 (2)
e isso só é verdade se α1 = ... = αn = 0.
Se dispusermos os vetores que desejamos analisar em uma matriz
quadrada A, como fizemos com a matriz dos coeficientes do sistema de
equações anterior, e calcularmos seu determinante, podemos ter dois
tipos de solução:
• se det A = 0, então os vetores são LD;
• se det A ≠ 0, então os vetores são LI.
LD: linearmente
dependente.
Glossário
64 Matemática para Computação
Para compreender esses conceitos, acompanhe o próximo exemplo.
Exemρlo 4
Sejam os vetores u = (1, 2, 3), v = (3, –1, 6) e w = (4, 2, 1). Queremos
classificar os três vetores em LI ou LD. Assim, fazemos:
A � �
1 2 3
3 1 6
4 2 1
Aplicando a regra de Sarrus, podemos escrever:
A � � � � �� � � � � � � � � � �� � � � � � � � � �
1 2 3
3 1 6
4 2 1
1 1 1 2 6 4 3 3 2 4 1 3 2 6 1 1 3 2 59
Logo, os vetores u, v e w são linearmente independentes, pois o
determinante de A resultou em um valor diferente de zero.
Portanto, pode-se usar as matrizes e suas operações – nesse caso,
o determinante – para analisar se os vetores que a compõem são
linearmente independentes. Conhecendo a quantidade de elementos
que está alocada nesses vetores e a dimensão do espaço a ser analisa-
do, é possível avaliar se esse espaço pode ser gerado por esses veto-
res. Com essas duas conclusões em mãos, podemos afirmar (ou não) a
existência de uma base de vetores para o espaço avaliado.
3.4 Fatoração matricial – Método de Gauss
Vídeo Computacionalmente, podemos trabalhar com matrizes com um
número muito grande de elementos.
Ao pensarmos, por exemplo, na análise de dados, nas redes de
computadores ou mesmo na área de inteligência artificial, o número
de elementos em uma matriz pode estar na casa dos milhares ou mais.
Portanto, é impossível realizarmos cálculos de maneira manual, sem a
utilização de uma ferramenta computacional.
Matrizes 65
Dessa forma, a correta manipulação desses dados dentro das matri-
zes é fundamental para que encontremos resultados coerentes.
Assim, vamos abordar, nesta seção, a fatoração (decomposição) de
matrizes, para que possamos viabilizar algoritmos que nos permitam
resolver determinantes, encontrar a inversa ou mesmo resolver gran-
des sistemas de equações, dentre outras aplicações.
Seja uma matriz Am⨯n dada por:
A
a a a a a
a a a
k m n
k
1
1 1
11
1
12
1
1
1
1
1
1
1
21
1
22 2
� �
� � � � � � � � � �
� � � � � �
�
� � �
� � aa a
a a a a a
m n
kk km kn
2 2
1
1
2
1
1 1
1 1 1
� � � �
� � � � � � � � � �
�
� � � � � � � �
� � �
� � �
k k
�� � � � �
� � �a a a a amk mm mnm m1
1
2
1 1 1 1� � � � � � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
E, ainda, seja A(k) uma matriz semelhante a A(1), já triangularizada:
A
a a a a a
a a a
k
k m n
k m
� �
� � � � � � � � � �
� � � � �
�
11
1
12
1
1
1
1
1
1
1
22
2
2
2
2
20
� � �
� � �� � �
� � � � � �
� �
�
� � � � � �
� � � � �
� � � � � � � �
� �
a
a a a
a
n
kk
k
km
k
kn
k
mk
k
2
2
0 0
0 0 aa amm
k
mn
k� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
A triangularização de matrizes é um dos processos mais práticos
para a resolução de diversos problemas dentro da álgebra, como aque-
les citados anteriormente.
Vamos entender esse processo de modo que seja possível
transcrevê-lo em formato de algoritmo.
Note que:
A M A
A M Am m
m
2
1
1
1
1
� � � �
� �
�
�� �
� �
� �
�
�
��
�
�
�
Portanto, precisamos de m – 1 passos para concluir a decomposi-
ção. Vamos escrever esse processo em etapas.
66 Matemática para Computação
Se a11
1 0� � � , então:
A = A
a a a a a
a a a
1
k m n
k
� �
� � � � � � � � � �
� � � �
�
11
1
12
1
1
1
1
1
1
1
21
1
22 2
1
� � �
� 11 1 1
1 1 1
2 2
1
1
2
1
� � � � � �
� � � � � � � � �
� �
� � � � � � � �
� � �
a a
a a a a a
m n
kk km knk k
��
� � � � � � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � � � � � �
� � �a a a a amK mm mnm m1
1
2
1 1 1 1
��
�
�
�
�
�
�
�
�
Assim, existe uma matriz M1 (m⨯m):
M
a
a
a
a
m
1
21
1
11
1
1
1
11
1
1
1
1
1
1
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
� �
..
..
..
��
�
�
�
�
�
�
�
�
�
�
�
�
Com:
m
a
a
� ��m
a
a
� �m
a
a
m
m
21
21
1
11
1 31
31
1
11
1 1
1
1
11
1
� � � � � � �
� �
� �
� �
� �
� �
, , , �� �
� � � �� �, .��tal�que�A M A2 1
1
Logo:
A
a a a a a
a a a
k m n
k m
2
11
1
12
1
1
1
1
1
1
1
22
2
2
2
2
20
� �
� � � � � � � � � �
� � � � �
�
� � �
� � �� � �
� � � � � � � �
�
� � � � � � � �
� � �
� � � � � � � �
a
a a a a
a
n
k kk km kn
m
2
2
2
2 2 2 2
2
2
0
0 �� � � � � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� � �a a amk mm mn
2 2 2
Note que M1 multiplica todas as colunas de A, mas só zera a coluna 1, abaixo da
posição (1, 1), ou, ocasionalmente, alguma outra coluna.
De
si
gn
-S
py
/S
hu
tte
rs
to
ck
PASSO
1
Matrizes 67
Se a22
2 0� � � , então existe uma matriz M2 (m⨯m), tal que A(3) = M2 · A(2) = M2 · M1 · A(1).
M
a
a
a
a
m
2
32
2
22
2
2
2
22
2
1
1
1
1
1
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
� �
��
�
�
�
�
�
�
�
Com:
m
a
a
� ��m
a
a
� �m
a
a�
m
m
32
32
2
22
2 42
42
2
22
2 2
2
2
� � � � � �
� �
� �
� �
� �
� �
, , ...,
222
2� � .
Logo:
A
a a a a a
a a a
k m n
k m
3
11
1
12
1
1
1
1
1
1
1
22
2
2
2
2
20
� �
� � � � � � � � � �
� � � � �
�
� � �
� � �� � �
� � � � � �
� �
�
� � � � � � � �
� � �
� � � � � � � �
� �
a
a a a
a
n
kk km kn
mk
2
2
3 3 3
3
0 0
0 0 aa amm mn
3 3� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
PASSO
2
De
si
gn
-S
py
/S
hu
tte
rs
to
ck
Se akk
k� � � 0, então A(k+1) = Mk · A(k).
A
a a a a
a a a
ak
k n
k n
�� �
� � � � � � � �
� � � � � �
�1
11
1
121
1
1
1
1
22
2
2
2
2
20
� �
� �
� � � kkk
k
kn
k
k k
k
k n
k
m k
a
a a
a
� � � �
� �
�� �
�
�� �
�
�
�
� � � � �
0 0 0 0
0 0
0 0 0 0
1 1
1
1
1
, ,
, 11
1 1k
m n
ka�� � �� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� ,
O processo deve ser seguido até o passo r, em que r = min{m – 1, n}.
Dessa forma, podemos escrever:
A(k+1) = Mk · A
(k) = Mk · Mk–1 · ... · M1 · A
(1).
De
si
gn
-S
py
/S
hu
tte
rs
to
ck
PASSO
K
68 Matemática para Computação
Mas por que todo esse procedimento? Porque sabemos que o
determinante de uma matriz pode ser calculado por meio da multipli-
cação dos elementos da diagonal principal; porém, também, porque
usaremos métodos de decomposição aplicados a outras operações
com matrizes, por exemplo, no cálculo da inversa de uma matriz. Além
disso, outro motivo é o computador resolver processos numéricos
discretos, por etapas, podendo, ainda, carregar muitos erros (de arre-
dondamento, truncamento e cancelamento).
Dessa forma, para implementar uma matriz e as operações sobre
esta, é necessário que tenhamos um passo a passo do processo numé-
rico. Transformar um problema matemático em um algoritmo nos ofe-
rece justamente esse passo a passo necessário para que o computador
possa resolvê-lo.
Agora, vamos colocar na prática os passos observados na teoria.
Exemρlo 5
Seja A �
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
1 1 5
4 1 2
. A decomposição de Gauss ocorrerá em
r = min{2, 3} = 2 passos. Então, fazendo o passo a passo, temos:
• Passo 1: a11 ≠ 0
M1
1 0 0
1
2
1 0
4
2
0 1
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
A M A2 1
1
1 0 0
1
2
1 0
4
2
0 1
2 4 2
1 1 5
4 1 2
� � � �� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
0 3 6
0 7 2
Cada algoritmo precisa
ser adaptado para uma
linguagem de programa-
ção específica. Se utili-
zarmos uma linguagem de
alto nível, possivelmente,
a própria linguagem já tra-
ga de maneira intrínseca
questões como armaze-
namento dos dados de
uma matriz na memória,
módulos de inversão,
cálculo do determinante
etc. Mas, se for uma
linguagem de baixo nível,
todas essas questões
serão declaradas pelo
programador. Sugerimos
a leitura dos seguintes
materiais, que trazem um
pouco da programação
usada em Python (alto ní-
vel) e em C++ (baixo nível)
em casos de aplicações
que usam matrizes:
• Aulas de introdução
à computação com
Python: matrizes.
Disponível em: https://panda.ime.usp.
br/aulasPython/static/aulasPython/
aula11.html. Acesso em: 6 jul. 2021.
• Curso de C: matrizes.
Disponível em: http://mtm.ufsc.
br/~azeredo/cursoC/aulas/c530.
html. Acesso em: 6 jul. 2021.
Leitura
https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html
https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html
https://panda.ime.usp.br/aulasPython/static/aulasPython/aula11.html
http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html
http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html
http://mtm.ufsc.br/~azeredo/cursoC/aulas/c530.html
Matrizes 69
• Passo 2: a22 ≠ 0
M2
1 0 0
0 1 0
0 7
3
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
A M A3 2
2
1 0 0
0 1 0
0 7
3
1
2 4 2
0 3 6
0 7 2
� � � �� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
0 3 6
0 0 12
Os elementos akk
k� � são os elementos pivôs.
O resultado obtido com o método de Gauss pode ser aplicado em
muitos contextos, como citamos anteriormente.
Usando esse método como “motor” para as nossas próximas de-
composições, vamos ver algumas possibilidades para a decomposição
matricial que podem agilizar o processo de cálculo computacional e mi-
nimizar os erros obtidos nesse processo.
3.5 Decomposição LU e LDU
Vídeo Nesta seção, apresentaremos alguns tipos de fatoração de matrizes
que serão úteis para a resolução de sistemas de equações lineares.
Esses processos de fatoração também são chamados de méto-
dos de decomposição. Iremos, então, estudar a decomposição LU e a
LDU. Esse último método ainda pode ser ramificado em outros mé-
todos, dependendo do tipo de matriz que tivermos. Vamos entender
esses processos.
3.5.1 Decomposição LU
Seja uma matriz A de ordem m. A decomposição dessa matriz em
outras duas matrizes, sendo a primeira uma matriz triangular infe-
rior L (lower) e a segunda uma matriz triangular superior U (upper), é
chamada de decomposição LU (FRANCO, 2006).
70 Matemática para Computação
A
a a
a a
l
l l
um
m mm m mm
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11 1
1
11
1
110�
� � �
�
�
� � �
�
��
� � �
�
u
u
L U
m
mm
1
0
�
�
�
�
�
�
�
�
�
�
� �
Esse tipo de decomposição não é único. Ou seja, podem existir dife-
rentes matrizes triangulares inferiores e superiores que, quando mul-
tiplicadas, originarão a matriz A. Assim, para encontrá-las, usamos o
processo de eliminação de Gauss, que nos auxilia a escrever a matriz A
na forma fatorada em matrizes mais simples.
É possível ter uma ideia da aplicação desse tipo de decomposição com a
leitura do artigo Estimação de estado em sistemas elétricos de potência: meto-
dologia para análise de observabilidade considerando medidas convencionais
e fasoriais. Nesse artigo, os autores fazem uso do método LU para tratar o
problema real transformado em modelo matemático.
Acesso em: 6 jul. 2021.
https://www.researchgate.net/publication/277717877_ESTIMACAO_DE_ESTADO_EM_SISTEMAS_ELETRICOS_DE_POTENCIA_
METODOLOGIA_PARA_ANALISE_DE_OBSERVABILIDADE_CONSIDERANDO_MEDIDAS_CONVENCIONAIS_E_FASORIAIS
Artigo
Como vimos, o processo de Gauss gera matrizes M1, M2, ... ,Mr , com
r = min{m – 1, n}, tal que:
A(r+1) = Mr ⋅ Mr–1 ⋅ ... ⋅ M1 ⋅ A
As matrizes M não são singulares, portanto podemos calcular suas
inversas. Assim:
A �M �M � � M �A r
r� � � � � �� � � �� �1
1
2
1 1 1
Portanto, L M M Mr� � ���
� � �
1
1
2
1 1 e U = A(r+1), com:
Triangular inferior Triangular superior
L M M M
m m m
r
r
� �
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
1
1
2
1 1
1 2
1
1
1
...
e
U
a
a
amm
m
�
� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
11
1
22
2
...
Para compreender como desenvolver a decomposição LU de uma
matriz, acompanhe o próximo exemplo.
Matrizes 71
Exemρlo 6
Seja A �
�
�
�
�
�
�
�
�
�
�
3 2 4
1 1 2
4 3 2
. Determine a decomposição LU da matriz A.
Usando a decomposição de Gauss, temos como primeiro pivô o ele-
mento na posição a11
1 3� � � .
Assim, os multiplicadores são: m
a
a
�e�m
a
a
21
21
1
11
1 31
31
1
11
1
1
3
4
3
� � � �
� �
� �
� �
� � .
A A m
m
� �
�
�
�
�
�
�
�
�
�
�
� ������ �
�
�
1
2 21 1
3 31 1
3 2 4
1 1 2
4 3 2
3 2 4
0 1
3
2
3
0 1
L L
L L
33
10
3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
O próximo pivô é a22
2 1
3
� � � . Então, o multiplicador é m
a
a
32
32
2
22
2
1
3
1
3
1� � �
� �
� � .
A
L m L
2
3 32 2
3 2 4
0 1
3
2
3
0 1
3
10
3
3 2 4
0 1
3
2
3
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �����
00 0 4�
�
�
�
�
�
�
�
�
�
�
�
�
Portanto, L carrega os multiplicadores (triangular inferior) e U é a
última matriz após a triangularização (triangular superior).
L �e�U�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 0 0
1
3
1 0
4
3
1 1
3 2 4
0 1
3
2
3
0 0 4
Além da decomposição LU, que, como vimos, não é única, pode-
mos nos basear nela para um outro tipo de decomposição, chamado
de LDU. Vamos entendê-lo na sequência.
Na linguagem MATLAB,
é possível usar as fun-
ções intrínsecas dessa
linguagem para calcular
a decomposição LU.
Assim, tendo a matriz A,
basta fazer:
>[L, U] = lu(A)
>[L, U, P] = lu(A)
Curiosidade
72 Matemática para Computação
3.5.2 Decomposição LDU
A decomposição LDU, ao contrário da LU, é única, desde que os
pivôs sejam diferentes de zero. Como o próprio nome nos leva a
perceber, A será fatorada (decomposta) em uma matriz triangular in-
ferior (L), uma matrizdiagonal (D) e uma matriz triangular superior (U)
na forma:
L ������D
d
d
dnn
�
�
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
1
1
11
22
...
��
�
�
� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�����U
1
1
1
1
Gauss pode ser aplicado sem troca de linhas ou colunas.
Dessa maneira,
A(n) = Mn–1 · ... · M1A
(1)
Assim,
A(n) = L–1 · A(1) = L-1 · A
Portanto, A = L · A(n), em que A(n) tem todos os pivôs akk
k� � � 0.
Definindo D
a
a
ann
n
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
11
1
22
2
...
, então D–1 existe e
D
a
a
ann
n
�
� �
� �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
11
1
22
2
1
1
1
...
Definindo U = D–1 · A(n), temos que: U
a
a
a
a
a
a
n
n�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
� �
� �
� �
1
1
1
12
1
11
1
1
1
11
1
2
2
22
2
...
��
�
�
�
�
�
�
�
�
�
�
�
�
Matrizes 73
E como:
L
m m mr
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
11 2
...
Então, A = L · A(n) = L · D(D-1 · A(n)) = LDU.
Assim, A pode ser decomposta da forma descrita. Acompanhe o
exemplo a seguir para praticar a decomposição em LDU de uma matriz.
Exemρlo 7
Decomponha a matriz A �
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1 2
1 5 3
4 9 1
em LDU.
Para decompor a matriz A em LDU, utilizamos a decomposição de
Gauss. Assim, calculamos M1 usando, inicialmente, o pivô a11
1 1� � � , e en-
contramos m
a
a
�e�m
a
a
�21
21
1
11
1 31
31
1
11
1
1
1
1 4
1
4� � � � � � � �
� �
� �
� �
� � .
Portanto, a matriz obtida é M1
1 0 0
1 1 0
4 0 1
� �
�
�
�
�
�
�
�
�
�
�
.
Desse modo, obtemos, nessa etapa, a matriz
A m
m
2
2 21 1
3 31 1
1 1 2
0 4 5
0 5 7
� �
�
�
� �����
�
� �
�
�
�
�
�
�
�
�
�
�
L L
L L
.
Agora, precisamos calcular M2 usando como pivôs
�a �e�m
a
a
22
2
32
32
2
22
2
4 5
4
� �
� �
� �� � � �
. Portanto, M2
1 0 0
0 1 0
0 5
4
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Assim, A L m L
3
3 32 2
1 1 2
0 4 5
0 0 3
4
� �
�
� �����
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Nesse momento, temos:
A �
� �
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�1 1 2
1 5 3
4 9 1
1 0 0
1 1 0
4 5
4
1
1 1 2
0 4 55
0 0 3
4
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� LU
74 Matemática para Computação
Agora, basta organizar U na forma:
U DU*� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 0 0
0 5 0
0 0 3
4
1 1 2
0 1 3
5
0 0 1
Portanto,
A �
� �
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1 2
1 5 3
4 9 1
1 0 0
1 1 0
4 5
4
1
1 0 0
0 5 0
00 0 3
4
1 1 2
0 1 3
5
0 0 1�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� LDU
Dependendo de como D é tratado, existem três tipos de decomposições:
1 2Decomposição de Doolittle (direto de
Gauss)
A = L · (D · U) = L · U’, em que lii = 1, ∀ i.
A �
�
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � � �
� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
1
...
.
Decomposição de Crout
A = (L · D) · U = L’ · U, em que uii = 1, ∀ i.
A �
�
� �
� � �
� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
...
1
1
1
3 Decomposição de Cholesky
A = Q · QT, em que lii = uii, ∀ i.
A
x
x
x
x
x
x
x
x
�
�
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Observação: a decomposição de Cholesky
pode ser encontrada baseada em Gauss, pois,
se A é simétrica, A = LDU e U = LT. Contudo, a
decomposição de Cholesky só é possível quando
A for uma matriz positiva definida por A = LDLT.
Se D > 0, então:
D
a
ann
1
2
11
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
...
... e
A L D D LT �Q Q T�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�· · · ·
1
2
1
2
Matrizes 75
Quando aplicamos os processos de decomposição para agilizar a
resolução de sistemas de equações, percebemos que cada tipo desses
sistemas se comporta melhor com uma decomposição específica. Se as
matrizes são esparsas, adotamos um método; se temos uma matriz em
blocos, podemos adotar outro.
O importante é termos o conhecimento prévio das ferramentas que
podem ser utilizadas, para que possamos definir, em cada caso, qual
a melhor estratégia de resolução, considerando a agilidade, a rapidez
computacional e a minimização de erros.
Uma matriz é denomi-
nada positiva definida se
os determinantes das n
submatrizes principais de
A forem positivos, ou seja:
|Akk| > 0, para todo
1 ≤ k ≤ n
A matriz identidade é
um exemplo de matriz
positiva definida.
Saiba mais
3.6 Inversa de uma matriz
Vídeo Há algumas maneiras de calcular a inversa de uma matriz. Uma de-
las exige o cálculo do determinante.
Como vimos, o determinante pode ser encontrado por meio da
triangularização de uma matriz. Após esse processo, basta multiplicar
os elementos da diagonal resultante.
Logo, pensando computacionalmente, o cálculo do determinante de
uma matriz depende de operações elementares (as quais não alteram
a solução do sistema) que podem ser descritas dos seguintes modos:
I. Permuta da i-ésima linha pela j-ésima linha.
Li ↔ Lj – é trocar as linhas, o que é equivalente a trocar a posição
das equações.
II. Multiplicação da i-ésima linha por um escalar não nulo λ.
Li → λLi – refere-se ao mesmo que multiplicar um número não
nulo na equação correspondente.
III. Substituição da i–ésima linha pela i–ésima linha mais λ vezes a
j–ésima linha.
Li → Li + λLj – corresponde a somar o múltiplo da outra equação.
Vamos praticar o cálculo do determinante de uma matriz, utilizando
as operações elementares.
A plataforma da Khan
Academy tem um material
muito interessante sobre
as operações aplicadas
sobre linhas e colunas
de uma matriz. Além da
leitura, é possível resolver
alguns exercícios sobre
o assunto.
Disponível em: https://pt.khana-
cademy.org/math/precalculus/
precalc-matrices/elementary-matrix-
-row-operations/a/matrix-row-ope-
rations. Acesso em: 6 jul. 2021.
Saiba mais
https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations
https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations
https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations
https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations
https://pt.khanacademy.org/math/precalculus/precalc-matrices/elementary-matrix-row-operations/a/matrix-row-operations
76 Matemática para Computação
Exemρlo 8
Seja a matriz A �
� �
�
�
�
�
�
�
�
�
�
�
�
�
2 2 3
1 1 3
2 0 1
, queremos calcular seu determinante
por meio de uma triangularização. Assim, aplicando operações elemen-
tares, temos:
� �
�
�
�
�
�
�
�
�
�
�
�
�
� ������
� �
� �
� �
2 2 3
1 1 3
2 0 1
2 2 3
0 0 9
2
0
3 3 1
2 2
1
2 1
L L L
L L L 22 4�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
� �����
� �
�
�
�
�
�
�
�
�
�
��
2 2 3
0 0 9
2
0 2 4
2 2 3
0 2 4
0 0 9
2
3 2L L
��
�
�
�
�
�
�
Nesse ponto, já temos uma matriz triangularizada; portanto,
det A �� � � � ��
�
�
�
�
� �2 2
9
2
18 .
Com base nesse princípio, desenvolvemos, na sequência, o cálculo
da inversa de uma matriz, conhecendo seu determinante.
3.6.1 Inversa de uma matriz por meio de determinantes
Uma das maneiras de encontrarmos a inversa de uma matriz qua-
drada A é por meio da matriz dos cofatores de A. Com esse resultado, é
possível obter a matriz adjunta de A e, na sequência, sua matriz inversa.
Dessa forma, inicialmente, precisamos conhecer o cofator de cada
um dos elementos de A, dados por:
Aij = (–1)
i+j |Mij|
Assim, Mij representa a matriz obtida da matriz original pela elimina-
ção da i-ésima linha e da j-ésima coluna.
É possível formar uma nova matriz, denominada de Ā, em que
Ā = [Aij]. Essa será a matriz dos cofatores.
Matrizes 77A transposição dessa matriz Ā origina a chamada matriz adjunta
de A, denotada por adj(A). Logo:
adj(A) = Āt
Com o conceito de determinante de uma matriz e de matriz ad-
junta, podemos enunciar um teorema que permite o cálculo da in-
versa de uma matriz A baseado nesses conceitos.
Teorema 1
Uma matriz quadrada A admite uma inversa se, e somente se, det (A) ≠ 0 (KOLMAN;
HILL, 2013). Nesse caso:
A
A
adj A� �
� � � �� �
1 1
det
Assim como as propriedades para as operações entre matrizes
ou mesmo as propriedades para o determinante de uma matriz,
destinamos, nesta seção, um espaço para tratarmos das proprie-
dades das matrizes invertíveis. São elas:
• Sejam duas matrizes quadradas A e B, de ordem n, com deter-
minante diferente de zero e, portanto, não singulares – o que
nos permite afirmar que são invertíveis. Portanto, se existe
A–1 e B–1, então A · B é invertível e (A · B)–1 = B–1 · A–1.
• Seja A uma matriz quadrada, de ordem n, com BA = I, portan-
to B é, também, de ordem n. Logo, A é invertível, ou seja, A–1
existe e, além disso, B = A–1.
• Dizemos que uma matriz A é semelhante a uma matriz B se, e
somente se, existir uma matriz invertível Q, tal que podemos
escrever A = Q–1 BQ.
Em todos os casos, podemos usar essas características algébri-
cas para otimizar os processos numéricos e agilizar a obtenção de
uma resposta.
Computacionalmente, encontramos muitas vantagens quando
podemos simplificar processos, e uma delas é a possibilidade de
diminuir o custo computacional. Ainda, é possível minimizar erros
quando reduzimos a quantidade de operações realizadas. Dessa
forma, o estudo das matrizes invertíveis e suas propriedades nos
traz um ganho em diferentes áreas e aplicações.
78 Matemática para Computação
3.6.2 Inversa de uma matriz por meio
do método de Gauss-Jordan
Vamos supor que uma matriz A, de ordem n, possa ser fatorada até
ser equivalente à matriz identidade:
In = Mk · Mk–1 · ... · M2 · M1 · A
Sendo assim, podemos multiplicar os dois lados da igualdade para
obtermos a matriz inversa de A, ou seja:
(In) · A
–1 = (Mk · Mk–1 · ... · M2 · M1 · A) · A
–1
A–1 = (Mk · Mk–1 · ... · M2 · M1) · In
Na prática, se temos uma matriz A, de ordem n, podemos escrever
essa matriz da forma:
[A│I]n⨯2n
Aplicando operações elementares sobre [A│I]n⨯2n, precisamos obter
[I│B]n⨯2x
com B = A–1.
Uma observação: se, ao realizar o procedimento, ocorrer uma linha
de zeros do lado esquerdo, significa que a matriz A não tem inversa.
Para comprovar esse resultado, basta calcular o determinante de A e
verificar que ele é igual a zero.
O exemplo a seguir esclarece como encontrar a inversa de uma ma-
triz por meio da triangularização, ou seja, pelo método Gauss-Jordan.
Exemρlo 9
Encontre a inversa de
2 6
1 3�
�
�
�
�
�
� .
Aplicando algumas operações elementares nessa matriz, obtemos:
2 6
1 3
1 0
0 1
1 3
1 3
1
2
0
0 112
2 1�
�
�
�
�
�
� � �� �
�
�
�
�
�
�
�
�
�
�
� ���
�
� � � �L L L
|
|
|
|
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 3
1 6
1
2
0
1
2
1
� �
|
|
O material sobre inversão
de matrizes do professor
Rodney Josué Biezuner
tem muitos exemplos
resolvidos. Sugerimos
a leitura deste mate-
rial, além de refazer os
exemplos e exercícios
presentes no texto.
Disponível em:
http://150.164.25.15/~rodney/
notas_de_aula/matrizes_inversas.
pdf. Acesso em: 17 jun. 2021.
Saiba mais
http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf
http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf
http://150.164.25.15/~rodney/notas_de_aula/matrizes_inversas.pdf
Matrizes 79
L L L
� � � �
2
6
3 2 1
1 3
0 1
1
2
0
1
12
1
6
1 0
0 1
1
�
� �
� ���
�
�
�
�
�
�
�
�
�
�
�
�
�
� ����
|
|
|
|
44
1
2
1
12
1
6
�
�
�
�
�
�
�
�
�
�
�
�
�
Portanto,
A� �
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
4
1
2
1
12
1
6
Com essas técnicas, relembramos os conceitos de vetores e matrizes,
além de fazermos a manipulação de operações sobres essas estruturas.
Percebam que o nosso foco foi trazer novas ferramentas e abor-
dagens que se adequem, de maneira mais suave, à necessidade de
aplicação computacional dos conceitos matemáticos.
Desse modo, são abordagens que, quando transformadas em algo-
ritmos, podem ser implementadas com facilidade, sendo que algumas
linguagens de programação já têm essa base matemática implemen-
tada para uso direto das operações.
Mesmo nesses casos, é importante saber o que está acontecendo por
trás da resposta obtida. Por esse motivo, sempre estimulamos que os
conceitos matemáticos envolvidos nas funções intrínsecas a cada uma
das linguagens de programação sejam avaliados antes do seu uso.
CONSIDERAÇÕES FINAIS
Neste capítulo, recordamos alguns conceitos estudados no ensino
médio e fundamental e aprendemos algumas teorias ainda não trabalha-
das no ensino básico.
O conceito de matriz é peça fundamental para a programação. Acre-
ditamos que o tripé teoria, prática e aplicação é necessário para a boa
compreensão de qualquer conceito ou disciplina. Por isso, sugerimos que
resolva os exercícios encontrados nas obras de referência bibliográfica,
acesse os links indicados como complementação do conteúdo e resolva o
máximo de exercícios possível sobre o tema.
80 Matemática para Computação
ATIVIDADES
Nas regras do xadrez, cada peça tem uma movimentação possível. Por
exemplo, o cavalo só pode se movimentar em “L”, ou seja,
• duas casas para a direita (ou para a esquerda) e uma para frente (ou
para trás);
• uma casa para a direita (ou para a esquerda) e duas casas para frente
(ou para trás).
A figura a seguir é um exemplo das possíveis movimentações que um
cavalo na casa 4D pode fazer.
8
7
6
5
4
3
2
1
HGFEDCBA
Explique, usando a notação “linha-coluna”, as possíveis movimentações
do cavalo branco que está na casa 1G (observação: ele não pode ficar
sobre outra peça branca).
Atividade 1
De acordo com o conceito de base para um espaço de vetores, indique
dois conjuntos de vetores que formam uma base para o ℝ³. Justifique o
porquê dessas escolhas.
Atividade 2
Explique por que afirmamos que a decomposição LU não é única.
Atividade 3
REFERÊNCIAS
FEOFILOFF, P. Vetores. IME, 2018. Disponível em: https://www.ime.usp.br/~pf/algoritmos/
aulas/array.html. Acesso em: 6 jul. 2021.
FRANCO, N. M. B. Cálculo numérico. 1. ed. São Paulo: Pearson Universidades, 2006.
KOLMAN, B.; HILL, D. R. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos
e Científicos, 2013.
LEON, S. J. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos e Científicos, 2019.
Sistemas de equações lineares 81
4
Sistemas de equações lineares
Os sistemas de equações são encontrados em uma gama de apli-
cações e nas mais diversas áreas. Das exatas às ciências biológicas,
passando pelas áreas tecnológicas e ciências sociais, resolver um sis-
tema de equações pode nos levar a resultados de balanceamentos
químicos, respostas de sistemas elétricos, equilíbrio de forças, distri-
buições de alimentos, dentre tantos outros.
De maneira mais conceitual, porém ainda aplicada, os sistemas de
equações nos permitem encontrar o que se relaciona nas diferentes
estruturas que os compõem, ou seja, pontos de intersecção, retas co-
muns ao sistema e planos que se interceptam.
Para resolver um sistema de equações, existem diversos métodos,
desde diretos e iterativos até exatos ou com solução aproximada, mas,
em todos os casos, se queremos expandir o conjunto de aplicações,
precisamos levar esses modos de resolução para um aspecto computa-
cional. Esse é o tema do capítulo sobre sistemas de equações lineares.
Com o estudo deste capítulo, você será capaz de:
• analisar a equivalência entre sistemas de equações lineares
e aplicar operações elementares sobre eles;
• resolver sistemas de equações de maneira direta e iterativa;
• analisar alguns algoritmos de resolução de sistemas de equa-
ções lineares, para incentivar o pensamento computacional;
• compreender as propriedadesinerentes aos sistemas trian-
gulares ou triangularizados;
• classificar os sistemas de equações lineares.
Objetivos de aprendizagem
82 Matemática para Computação
4.1 Sistemas equivalentes e operações
Vídeo Aprender a resolver os mais diversos tipos de sistemas de equações,
de maneira exata ou aproximada, é uma tarefa de grande necessidade
dentro das ciências. Antes de discorrermos sobre as diferentes aborda-
gens e métodos de resolução, discutiremos, nas subseções a seguir, sobre
a estrutura de um sistema de equações lineares e como podemos realizar
operações nesse tipo de sistema.
4.1.1 Sistemas equivalentes
Analisar a equivalência entre objetos é compará-los, dois a dois, de
acordo com algumas propriedades. A definição de sistemas equivalen-
tes está descrita a seguir.
Definição 1
“Dois sistemas de equações lineares envolvendo as mesmas variáveis são equivalen-
tes se, e somente se, tiverem o mesmo conjunto solução” (LEON, 2019, p. 4).
Dessa maneira, vamos supor um sistema AX1 = B e um segundo sis-
tema QX2 = C. Se X1 = X2, os dois sistemas serão equivalentes.
Exemρlo 1
O sistema
3 4 2
8
2 1
1 2 3
1 2 3
2 3
x x x
x x x
x x
� � �
� � � �
� � �
�
�
�
�
� ��
é equivalente ao sistema
3 4 2
4
3
1
3
26
3
3
2
12
1 2 3
2 3
3
x x x
x x
x
� � �
� � �
�
�
�
�
�
�
�
�
�
� ��
,
pois ambos apresentam como solução o vetor X �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
23
2
9
2
8
.
A definição e o exemplo nos levam a pensar que, se temos um siste-
ma no qual A é uma matriz complicada de ser resolvida, ou seja, exige
Sistemas de equações lineares 83
muitos cálculos, podemos transformá-la em uma matriz semelhante,
mais simples, por exemplo, uma matriz triangular, de modo que não
alteremos a solução do sistema.
Dessa maneira, temos na definição de matrizes equivalentes uma fer-
ramenta essencial para nos auxiliar na resolução de sistemas de equações.
Mas quais são as operações que podem ser aplicadas para essa
transformação na matriz sem que o sistema seja alterado? No tópico a
seguir, vamos apresentar as operações e aplicar em alguns exemplos.
4.1.2 Operações elementares
Um dos modos mais rápidos de encontrar o conjunto solução para
um sistema de equações lineares é por meio do chamado escalonamen-
to da matriz ampliada.
Uma matriz é denominada escalonada quando o número de zeros
ao lado esquerdo do primeiro elemento não nulo da linha aumenta a
cada linha. Por exemplo, a matriz a seguir está escalonada.
1 2 0 1
0 2 0 1
0 0 1 0
0 0 0 3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
No caso de ter esgotado o número de colunas, isto é, quando uma
linha se torna nula, todas as linhas seguintes devem ser linhas nulas.
Para obter uma matriz escalonada, com base em uma matriz amplia-
da do sistema de equações lineares, utilizamos operações elementares,
como a seguir.
O vídeo Exemplo prático:
sistemas equivalentes de
equações, da plataforma
Khan Academy, é um
conteúdo interessante
sobre o tema sistemas de
equações. Além de assistir
ao vídeo, você pode resol-
ver exercícios usando a
plataforma, que é gratuita,
gamificada e adaptativa.
Essa prática te ajudará a
fixar o conteúdo.
Disponível em: https://pt.kha-
nacademy.org/math/algebra/
systems-of-linear-equations/
equivalent-systems-of-equa-
tions/v/identifying-equivalent-
-systems-of-equations. Acesso
em: 14 jun. 2021.
Vídeo
Permuta da i-ésima linha pela j-ésima linha. A troca de linhas corresponde à troca de posição das equações,
o que não influencia na solução do sistema.
Li ↔ Lj
Multiplicação da i-ésima linha por um escalar não nulo λ. Equivale a multiplicar um número não nulo na
equação correspondente, que também não altera a solução.
Li → λLi
Substituição da i-ésima linha pela i-ésima linha mais λ vezes a j-ésima linha. Equivale a somar o múltiplo da
outra equação, que também não altera a solução do sistema.dav
oo
da
/ S
hu
tte
rs
to
ck
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
https://pt.khanacademy.org/math/algebra/systems-of-linear-equations/equivalent-systems-of-equations/v/identifying-equivalent-systems-of-equations
84 Matemática para Computação
Li → Li + λLj
As operações realizadas em uma matriz ampliada resultam em uma
matriz equivalente. Conforme o exemplo a seguir ilustra.
Exemρlo 2
O sistema
3 4 2
8
2 1
1 2 3
1 2 3
2 3
x x x
x x x
x x
� � �
� � � �
� � �
�
�
�
�
� ��
, apresentado no Exemplo 1, pode ser
escrito na forma de matriz ampliada como
3 1 4
1 1 1
0 2 1
2
8
1
3 1 4
0 4
3
1
3
0 2 1
2
26
3
1
2
1
3 1
�
� � �
�
�
�
�
�
�
�
�
�
�
�
� ����
�
�
�
�L L
��
�
�
�
�
�
�
�
�
�
�
�
�
�
Aplicando as operações anteriormente elencadas, fazemos
3 1 4
1 1 1
0 2 1
2
8
1
3 1 4
0 4
3
1
3
0 2 1
2
26
3
1
2
1
3 1
�
� � �
�
�
�
�
�
�
�
�
�
�
�
� ����
�
�
�
�L L
��
�
�
�
�
�
�
�
�
�
�
�
�
�
Na sequência, desenvolvemos
3 1 4
0 4
3
1
3
0 2 1
2
26
3
1
3 1 4
0 4
3
1
3
0 0 3
3
3
2 2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� ����
�
�
�L L
22
12
2
26
3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Note que, após a aplicação de operações elementares, obtemos
uma matriz ampliada escalonada, sendo que podemos transcrevê-la
da forma matricial para a forma de sistema.
3 4 2
4
3
1
3
26
3
3
2
12
1 2 3
2 3
3
x x x
x x
x
� � �
� � �
�
�
�
�
�
�
�
�
�
� ��
De acordo com Leon (2019), dois sistemas que possuem matrizes
ampliadas equivalentes têm o mesmo conjunto solução. Dessa manei-
ra, podemos definir:
Sistemas de equações lineares 85
Definição 2
“Desde que possuam matizes ampliadas equivalentes, os sistemas podem ser deno-
minados sistemas equivalentes” (LEON, 2019, p. 4).
Uma importante característica dos sistemas de equações lineares é
a possibilidade de verificação da solução (prova real). Para isso, basta
substituirmos a solução encontrada nas equações originais, como é de-
senvolvido no exemplo a seguir.
Exemρlo 3
No Exemplo 1, afirmamos que os sistemas
3 4 2
8
2 1
1 2 3
1 2 3
2 3
x x x
x x x
x x
� � �
� � � �
� � �
�
�
�
�
� ��
e
3 4 2
4
3
1
3
26
3
3
2
12
1 2 3
2 3
3
x x x
x x
x
� � �
� � �
�
�
�
�
�
�
�
�
�
� ��
eram equivalentes porque tinham a mesma solução.
Assim, verificamos que eles realmente têm essa característica.
Como X �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
23
2
9
2
8
, então, substituindo essa solução no primeiro
sistema, temos que
3 23
2
9
2
4 8 2
23
2
9
2
8 8
2 9
�
�
�
�
�
�
� � �
�
�
�
�
�
� � � � �
� �
�
�
�
�
�
� � �
�
�
�
�
�
� � � � �
�
22
8 1�
�
�
�
�
� � � � � �
�
�
�
�
��
�
�
�
�
�
��
E o mesmo pode ser feito no segundo sistema:
3 23
2
9
2
4 8 2
4
3
9
2
1
3
8 26
3
3
2
�
�
�
�
�
�
� � �
�
�
�
�
�
� � � � �
�
�
�
�
�
�
� �
�
�
�
�
�
� � � � �
88 12� � �
�
�
�
�
��
�
�
�
�
�
��
Como ambos os sistemas têm X como solução, eles são sistemas
equivalentes.
86 Matemática para Computação
Com os sistemas equivalentes e operações definidos, veremos na
sequência a aplicação de inversão de matrizes para a solução de um
sistema de equações.
4.1.3 Análise da matriz inversa
Um sistema linear da forma AX = B com A sendo uma matriz de coefi-
cientes quadrada pode ser resolvido com a aplicação de matrizes inversas.
Note que, para esse tipo de aplicaçãoser possível, devemos ter sis-
temas de equações bem específicos (com n equações e n variáveis).
Outra questão importante é a necessidade de que A seja invertível, ou
seja, que tenha det A ≠ 0.
Se essas exigências são verificadas, podemos escrever:
Definição 3
Seja A uma matriz n⨯n com A invertível, então é válida a sequência de cálculos
a seguir:
I. AX = B.
II. A-1 · (AX) = A-1 · B.
III. In · X = A-1 · B.
IV. X = A-1 · B.
Portanto, se A cumpre essas condições, temos que X = A-1 · B será a
solução única para o sistema determinado.
4.2 Sistemas triangulares e escalonados
Vídeo O processo que permite o escalonamento de uma matriz tem como
fundamentação teórica o método de Gauss (fatoração ou eliminação
gaussiana), que nos permite escrever um sistema de equações lineares
na sua forma triangular superior.
Por meio de um sistema de equações lineares na forma triangula-
rizada (inferior ou superior), é possível encontrar a solução utilizando
substituições progressivas (triangular inferior) ou regressivas (triangu-
lar superior). Vamos entender esse processo.
No vídeo Testando uma
solução para um sistema
de equações, do canal da
Khan Academy Brasil,
você poderá rever esse
procedimento sendo
aplicado em outros siste-
mas de equações. É uma
ferramenta poderosa
para verificar se a solução
encontrada está correta.
Disponível em: https://youtu.be/
sxJHonr96kA. Acesso em: 14 jun. 2021.
Vídeo
Sugerimos que você assis-
ta ao vídeo Escalonamento,
disponível no canal Portal
da Matemática OBMEP.
Com ele, é possível reca-
pitular a decomposição
gaussiana e começar a
aplicá-la no contexto dos
sistemas de equações
lineares.
Disponível em: https://www.youtu-
be.com/watch?v=QmmYqR-7zm4.
Acesso em: 14 jun. 2021.
Vídeo
https://youtu.be/sxJHonr96kA
https://youtu.be/sxJHonr96kA
https://www.youtube.com/watch?v=QmmYqR-7zm4
https://www.youtube.com/watch?v=QmmYqR-7zm4
Sistemas de equações lineares 87
Seja um sistema de equações lineares da forma LX = B, com
• L
l �
l ln nn
�
�
�
�
�
�
�
�
�
�
�
11
1
0�
� � �
�
• X
x
xn
�
�
�
�
�
�
�
�
�
�
�
1
• B
b
bn
�
�
�
�
�
�
�
�
�
�
�
1
Portanto, esse é um sistema triangular inferior no qual a matriz dos
coeficientes, L, tem seus elementos na forma lij = 0 para i < j.
Portanto,
l x b
l x l x b
l x l x l x bn n nn n n
11 1 1
21 1 22 2 2
1 1 2 2
�
� �
� � � �
�
�
�
�
�
�
�
� � � �
�
Podemos montar algoritmos para calcular a solução de sistemas li-
neares com essa característica e que poderão ser reescritos na lingua-
gem de programação desejada.
Para estruturar tal algoritmo, usaremos uma linha genérica li, tal que
li1 · x1 + li2 · x2 + ⋯ + lii · xi = bi
Dessa maneira, isolando xi, obtemos
x
b l l x l x
li
i i i ii i
ii
�
� � � � � �( )1 2 2 1 1
Portanto, podemos denotar esse raciocínio como o algoritmo a seguir.
Algoritmo 1
x b
l1
1
11
=
Para i = 2, ..., n faça
x
b l x
li
i ij j
j
i
ii
�
�
�
�
�
��
�
�
�
���
�
�
1
1
m
yd
eg
ag
e/
Sh
ut
te
rs
to
ck
88 Matemática para Computação
Para compreender melhor o Algoritmo 1, acompanhe o exemplo a
seguir.
Exemρlo 4
Seja um sistema de equações lineares triangular inferior da forma
1 0 0
2 3 0
1 2 1
2
2
1
1
2
3
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
x
x
x
Vamos resolver esse sistema usando o Algoritmo 1. Assim,
x
b
l1
1
11
2
1
2� � � � �
x
b l x
l2
2 21 1
22
2 2 2
3
2 4
3
2�
�
�
� �� �
�
�
�
�
� �
x
b l x l x
l3
3 31 1 32 2
33
1 1 2 2 2
1
1 2 4
1
5�
� �
�
� �� � �� � � �� � �� �
�
� �
� �
Portanto, S = {–2, –2, –5}.
O mesmo princípio é adotado em um sistema de equações lineares
triangular superior (forma padrão obtida por meio do escalonamento).
Nesse caso, usaremos como modelo um sistema de equações linea-
res da forma UX = B, com
• U �
�
�
�
�
�
�
�
�
�
�
u � u
u
n
nn
11 1
0
�
� � �
�
• X
x
xn
�
�
�
�
�
�
�
�
�
�
�
1
• B
b
bn
�
�
�
�
�
�
�
�
�
�
�
1
Sistemas de equações lineares 89
Portanto, esse é um sistema triangular superior no qual a matriz
dos coeficientes, U, tem seus elementos na forma uij = 0 para i > j.
Denotamos
u x u x u x b
u x u x b
u x b
n n
n n
nn n n
11 1 12 2 1 1
22 2 2 2
� � � �
� � � �
�
�
�
�
�
�
�
�
�
�
� � � �
��
Também podemos montar um algoritmo para a solução dos siste-
mas no formato UX = B e, para isso, usaremos a i-ésima linha da forma:
uii · xi + uii+1 · xi+1 + uii+2 · xi+2 + ... + uin · xn = bi
Isolando xi, obtemos
xi = bi – ui(i+1) · xi+1 – ui(i+2) · xi+2 – ... – uin · xn
Portanto, podemos escrever esse raciocínio da seguinte maneira:
Algoritmo 2
x b
un
n
nn
=
Para i = (n – 1), (n – 2), ..., 1, faça:
x
b u x
u
u xi
i
j i
n
ij j
ii
ij j�
�
�
�
�
�
�
�
�
�
�
�� �� �
�
1
Exemρlo 5
Seja um sistema de equações lineares triangular superior da forma:
1 2 1
0 3 0
0 0 1
2
2
1
1
2
3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
x
x
x
m
yd
eg
ag
e/
Sh
ut
te
rs
to
ck
90 Matemática para Computação
Usando o Algoritmo 2, resolvemos esse sistema da seguinte forma:
x
b
u3
3
33
1
1
1= = =
x
b u x
u2
2 23 3
22
2 0 1
3
2
3
�
�
�
� � �
�
� �
x
b u x u x
u1
1 12 2 13 3
11
2 2 2
3
1 1
1
13
3
�
� �
�
� � �� � ��
�
�
�
�
� � � �
� �
Logo, a solução para esse sistema de equações é S � � ���
�
�
�
�
13
3
2
3
1, , .
Devemos notar que os algoritmos não dependem de linguagem de
programação previamente escolhida e precisam ser adaptados à lin-
guagem que queremos programar.
4.2.1 Classificação de um sistema de equações lineares
Começaremos esse tópico elencando três exemplos simples
(Figura 1) que serão resolvidos de forma escalonada e usados para
exemplificar os tipos de soluções possíveis em um sistema de equa-
ções lineares. Vamos utilizar uma calculadora on-line para resolver o
escalonamento .
Figura 1
Sistemas de equações escalonados por meio de calculadora on-line
Sistema Escalonamento por meio de calculadora on-line
x x
x x
1 2
1 2
2
3 2 3
� �
� �
�
�
�
��
�
�
�
��
�
�
��
1 1
3 2
2
3
1 1 2
0 1 3� �
�
�
��
�
�
��· (–3) L2 – 3 · L1 → L2
x x
x x
1 2
1 2
2 3
3 6 9
� �
� �
�
�
�
��
1 2
3 6
3
9
�
�
��
�
�
��
�
1 2 3
0 0 0
�
�
��
�
�
��· (–3) L2 – 3 · L1 → L2
x x
x x
1 2
1 2
2 3
3 6 3
� �
� �
�
�
�
��
1 2
3 6
3
3
�
�
��
�
�
��
�
· (–3) L2 – 3 · L1 → L2
1 2 3
0 0 6�
�
�
��
�
�
��
Fonte: Elaborada pela autora.
https://matrixcalc.org/pt/slu.html
Sistemas de equações lineares 91
Mediante o processo de escalonamento da matriz ampliada, o siste-
ma de equações lineares pode ser resolvido por meio de substituições
regressivas.
Ao observarmos o primeiro sistema de equações da Figura 1, temos
que, se as matrizes ampliadas são equivalentes, a solução do sistema
gerado pela matriz escalonada é equivalente à solução do sistema ori-
ginal. Assim, podemos escrever:
x x
x
1 2
2
2
3
� �
� � �
�
�
�
��
Logo, x2 = 3 e x1 = –1.
Observando graficamente 1 essas duas retas que formam o nosso
sistema de equações lineares, obtemos:
Figura 2
Sistema de equações x x
x
1 2
2
2
3
� �
� � �
�
�
�
eq1: x + y = 2
eq2: –y = –3
y
9
8
7
6
5
4
3
2
1
1–1–2–3–4–5–6–7–8–9–10–11–12 2 3 4 5 6 7 8 90
–1
x
A = (–1, 3)
Fonte: Elaborada pela autora.
Observamos que as retas formadas pela eq1 e eq2 se interceptam
em um ponto que, não por acaso, é a solução do sistema. Ou seja, a so-
lução de um sistema de equações é justamente o ponto de intersecção
das retas que formam esse sistema. Entretanto, o que ocorre nos siste-
mas de equações seguintes?
No segundo sistema de equações da Figura 1, após o escalonamen-
to, podemos escrever o sistema de equações equivalente da seguinte
maneira:
x x
x x1 2 1 2
2 3
0 0
2 3
� �
�
� � �
Para obter esse gráfico,
utilizamos o software
GeoGebra on-line.
Disponível em: https://www.
geogebra.org/graphing/jxrjp8dc.
Acesso em: 15 jul. 2021.
1
https://www.geogebra.org/graphing/jxrjp8dchttps://www.geogebra.org/graphing/jxrjp8dc
92 Matemática para Computação
Observe o gráfico a seguir formado pelas retas.
Figura 3
Sistema de equações x x
x x
1 2
1 2
2 3
3 6 9
� �
� �
�
�
�
eq1: x + 2y = 3
eq2: 3x + 6y = 9eq2: 3x + 6y = 9
y
2
2
4
44
6
6
8
8
10
10
12
12–2
–2
–4–6–8–10–12–14–16–18 0
x
Fonte: Elaborada pela autora.
Observamos que eq1 e eq2, presentes na Figura 3, se sobrepõem,
isto é, são retas coincidentes. Portanto, nesse caso, afirmamos que
temos infinitos pontos de intersecção, o que nos permite concluir que
temos infinitas soluções para o sistema de equações.
Vamos fazer o mesmo com o terceiro sistema de equações da Fi-
gura 1. Primeiro, reescreveremos o sistema de equações equivalente
escalonado da seguinte forma:
x x
x x
1 2
1 2
2 3
0 0 6
� �
� � �
O qual representamos graficamente como:
Figura 4
Sistema de equações x x
x x
1 2
1 2
2 3
3 6 3
� �
� �
�
�
�
eq1: x + 2y = 3
eq2: 3x + 6y = 3eq2: 3x + 6y = 3
y
2
2
4
44
6
6
8
8
10
10
12
12–2
–2
–4–6–8–10–12–14–16–18 0
x
Fonte: Elaborada pela autora.
Cr
ea
te
d
by
G
eo
Ge
br
a
Cr
ea
te
d
by
G
eo
Ge
br
a.
Sistemas de equações lineares 93
Já no sistema de equações
x x
x x
1 2
1 2
2 3
3 6 3
� �
� �
�
�
�
��
, as equações eq1 e eq2
são paralelas, o que nos mostra que não têm pontos de intersecção. Isso
significa que o último sistema de equações representado na Figura 1
não tem solução.
Assim, podemos afirmar que existem três tipos de soluções possí-
veis para um sistema de equações lineares:
I. quando existe uma única solução, denomina-se sistema compatível
e determinado;
II. quando existem infinitas soluções, denomina-se sistema
compatível e indeterminado;
III. quando não existe solução, denomina-se sistema incompatível.
Desejamos criar uma generalização para esse conceito para que
possamos classificar um sistema de equações com base em sua matriz
dos coeficientes e em sua matriz ampliada escalonada. Desse modo,
introduziremos o conceito de posto de uma matriz.
Definição 4
O posto p de uma matriz A é o número máximo de linhas não nulas após o seu
escalonamento.
Denotamos o posto da matriz dos coeficientes por pc e o posto da
matriz ampliada por pa. Assim, seja um sistema de equações da forma:
a x a x b
a x a x b
n n
m mn n m
11 1 1 1
1 1
� � �
� � �
�
�
�
�
�
�
� � �
�
Com matriz dos coeficientes
a a
a a
n
m mn
11 1
1
�
� � �
�
�
�
�
�
�
�
�
�
�
�
e matriz ampliada dada
por
a a b
a a b
n
m mn m
11 1 1
1
�
� � � �
�
�
�
�
�
�
�
�
�
�
�
.� Classificamos:
I. Se pc = pa, o sistema é compatível.
a. Se pc = pa = n, em que n é o número de variáveis do sistema, o
sistema é compatível e determinado (solução única).
b. Se pc = pa < n, o sistema é compatível e indeterminado (infinitas
soluções).
II. Se pc < pa, o sistema é incompatível.
O material da aula Sistemas
de equações lineares e ma-
trizes, do professor Daniel
Norberto Kozakevich, traz,
além da teoria relacionada
à classificação dos sistemas
de equações lineares,
muitos exemplos resolvi-
dos. Sugerimos que eles
sejam refeitos para fixar o
conteúdo aprendido nesta
subseção.
Disponível em: http://www.mtm.ufsc.
br/~daniel/7105/aula_3.pdf. Acesso
em: 15 jun. 2021.
Saiba mais
http://www.mtm.ufsc.br/~daniel/fotos.htm
http://www.mtm.ufsc.br/~daniel/7105/aula_3.pdf
http://www.mtm.ufsc.br/~daniel/7105/aula_3.pdf
94 Matemática para Computação
Reunimos no Quadro 1 os conceitos e as definições abordados até
o momento. É importante notar que, para essa representação, escolhe-
mos alguns sistemas de equações lineares como exemplo, para uma
melhor compreensão dos resultados.
Quadro 1
Síntese de conceitos
Primeiro sistema Segundo sistema Terceiro sistema
Sistema de
equações
x x
x x
1 2
1 2
2
3 2 3
� �
� �
�
�
�
��
x x
x x
1 2
1 2
2 3
3 6 9
� �
� �
�
�
�
��
x x
x x
1 2
1 2
2 3
3 6 3
� �
� �
�
�
�
��
Matriz dos
coeficientes
1 1
3 2
1 1
0 1
�
�
�
�
�
� � �
�
�
�
�
�
�
1 2
3 6
1 2
0 0
�
�
�
�
�
� �
�
�
�
�
�
�
1 2
3 6
1 2
0 0
�
�
�
�
�
� �
�
�
�
�
�
�
pc pc = 2 pc = 1 pc = 1
Matriz
ampliada
1 1 2
3 2 3
1 1 2
0 1 3
�
�
�
�
�
� � � �
�
�
�
�
�
�
1 2 3
3 6 9
1 2 3
0 0 0
�
�
�
�
�
� �
�
�
�
�
�
�
1 2 3
3 6 3
1 2 3
0 0 6
�
�
�
�
�
� � �
�
�
�
�
�
�
pa pa = 2 pa = 1 pa = 2
Posto pa = pc = n pa = pc < n pc < pa
Denominação Compatível e determinado Compatível e indeterminado Incompatível
Fonte: Elaborado pela autora.
Percebemos que, por meio da análise da matriz dos coeficientes e
da matriz ampliada, podemos classificar sistemas de equações de qual-
quer tamanho, ou seja, formados por m equações e n variáveis.
4.3 Eliminação gaussiana
Vídeo
Agora, vamos resolver um sistema de equações lineares para que
possamos, por intermédio desse desenvolvimento, definir o método da
eliminação gaussiana usando, para isso, a fatoração matricial (decom-
posição gaussiana).
Desse modo, seja:
2 4 2 6
5 0
4 2 2
1 2 3
1 2 3
1 2 3
x x x
x x x
x x x
� � �
� � �
� � �
�
�
�
�
�
Sistemas de equações lineares 95
Portanto, pela fatoração matricial, escrevemos
A A
M
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
2 4 2
1 1 5
4 1 2
� ����� �����
multiplicandopor
�� �
�
�
�
�
�
�
�
�
�
�
�
�
�
A
M
2
2
2 4 2
0 3 6
0 7 2
� ����� �����
multiplicandopor
�� �
�
�
�
�
�
�
�
�
�
�
�
�
�
A3
2 4 2
0 3 6
0 0 12
O que faz o M1? Zera todos os elementos abaixo da posição (1, 1).
O que faz o M2? Zera todos os elementos abaixo da posição (2, 2).
Com isso, ao invés de resolvermos A1 · x = b, resolvemos A3 · x = c,
em que:
A2 = M1 · A1
A3 = M2 · A2 = M2 · M1 · A1
e
M2 · M1 · A1 · x = M2 · M1 · b = c
Com base nesse exemplo, podemos definir:
Definição 5
Uma matriz elementar triangular inferior de ordem n e índice k pode ser escrita
como:
M I men k
T� �
Em que e mi
T � �0 , para i = 1, …, k e m
m
m
mn
�
�
�
�
�
�
�
�
�
�
�
�
�
1
2
...
é ortogonal a todos os vetores
canônicos e1, e2, ..., ek.
Então,
1 0 0 0 0
1
2
1... ...
�� ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
m
m
m
m
n
0 1 0 0 0
1
2
2... ...
�� ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �
m
m
m
m
n
96 Matemática para Computação
0 1 0 0
1
2...
...
posição�k
n
k
m
m
m
m
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �� 0
Dessa forma, temos:
M
m
m
k
n
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
1
0
0
0 0
1
...
...
. ... 11 0
1
1
1
0
posição�k
...
...
...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
00 0 0 0
0 0 0 0 0
0 0
0 0
1
...
...m
m
k
n
coluna�k
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Logo,
M
m
m
k
n
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 0 0 0 0
0 0 1 0 0
0 0
0 1
1
...
...
(1)
é a matriz elementar triangular inferior de ordem n e índice k. Com a
matriz elementar, podemos extrair os seguintes resultados:
• Resultado 1: se M �I � �m �en k
T� � � , então M �I � �m �en k
T� � � �1 .
• Resultado 2: dado x, com xk ≠ 0, existe uma única matriz elemen-
tar triangular M, de índice k, que anula todos os elementos de x
abaixo da posição k, mantendo todos os demais.
De acordo com a fatoração gaussiana, se A é uma matriz com m
linhas e n colunas, então temos m – 1 passos para obter a matriz A(m),
tal que
A(1) → A
(2) = M1 · A
(1) → ... → A(m) = Mm–1 · A
(m–1)
Sistemas de equações lineares 97
Assim, generalizando esse processo e escrevendo por meio de ma-
trizes elementares, teremos
A(k+1) = Mk · A
(k) = Mk · Mk–1 · ... · M1 · A
(1)
em que
M �I � �m �ek n k
T� � �
Logo,
A I m e Ak n k k
T k�� � � �� �� � �1
� ���� ����
Mk
Que matricialmente é escrito como
A A m
m
ak k
k k
m k
kk
k�� � � �
�
� �� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�1
1
0
0
0 0
,
,
... aakn
k� ��
��
�
��
Portanto,
A A
�
m a
k k k k
k k kk
k
�� � � �
�� �� �
� � � �
� � � �
� � �
� � �
1
1
0 0 0 0
0 0 0 0
0 0
0 0 0
,
, mm a
x
m a m a a
k k kn
k
m k kk
k
m k kk
k
kn
k
�
� �
� � � � � �
� � � �
� � �
�
�
�
�
�
1
0
0 0 0
,
, ,
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
que apresenta o processo de atualização de A(k).
A matriz A(k+1) pode ser obtida por intermédio da matriz A(k), basta
alterarmos o canto inferior direito, isto é,
a aij
k
ij
k�� � � ��1 , i = 1, ..., k e j = 1, ..., n
a aij
k
ij
k�� � � �� �1 0 , i = k + 1, ..., m e j = 1, ..., k
Logo,
a a m a �i k m�
j k n
ij
k
ij
k
ik kj
k�� � � � � �� � � � �
� �
1 1
1
, ,...,
,...,
98 Matemática para Computação
Esse processo nos permite escrever o algoritmo a seguir:
Algoritmo 3 – Decomposição de Gauss da matriz A
Seja A mxn∈ , m > 1, r = min{m – 1, n} akk
k� � � 0
A
a a a a a
a a a a
k m n
k m
�
� � � � � � � � � �
� � � � � �
11
1
12
1
1
1
1
1
1
1
22
2
2
2
2
2
� � �
� � � � 22
2
1 2
n
kk
k
km
k
kn
k
k mm
m
a a a
�
m m m a
� �
� � � � � �
� � � � � � � �
� � � � �
� � � � � � � �
� � ��� � �� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1� amn
m
Em que mk são as posições abaixo da diagonal que são zeradas.
Assim, para k = 1, 2, ..., r podemos escrever:
a m a
a
i k mik ik ik
kk
� � � �, ,...,1
a a m a i k m
j k n
ij ij ik kj� � � � �
� �
, ,...,
,...,
1
1
Observação: os elementos akk
k� � são chamados de elementos pivôs.
m
yd
eg
ag
e/
Sh
ut
te
rs
to
ck
Vamos acompanhar o próximo exemplo para compreender como
utilizar o Algoritmo 3.
Exemρlo 6
Seja A �
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
1 1 5
4 1 2
, a decomposição de Gauss ocorrerá em
r = min{2, 3} = 2 passos. Então, fazemos:
• Passo 1: a11 ≠ 0
M1
1 0 0
1
2
1 0
4
2
0 1
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Sistemas de equações lineares 99
A M A2 1
1
1 0 0
1
2
1 0
4
2
0 1
2 4 2
1 1 5
4 1 2
� � � �� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
0 3 6
0 7 2
• Passo 2: a22 ≠ 0
M2
1 0 0
0 1 0
0 7
3
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
A M A3 2
2
1 0 0
0 1 0
0 7
3
1
2 4 2
0 3 6
0 7 2
� � � �� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
2 4 2
0 3 6
0 0 12
Se o Algoritmo 3 for aplicado, a matriz encontrada será:
A 3
2 4 2
1
2
3 6
2 7
3
12
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
O método de eliminação de Gauss pode ser observado, na subseção
a seguir, mediante o chamado pivoteamento completo ou pivoteamento
parcial.
4.3.1 Pivoteamento completo
Seja a matriz A(k) da forma
A
a
a
k kk
k
lk ck
k
� �
� �
� ��
� � � �
� �
� �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
100 Matemática para Computação
Caso o pivô akk
k� � � 0 e os demais a �� ��ak k
k
m k
k
�
� � � �
1, ,, ..., forem diferentes de
zero, então podemos realizar o chamado pivoteamento completo.
Nesse caso, trocamos akk
k� � por alk ck
k
,
� � . Para isso, fazemos a troca en-
tre as linhas kk e lk e as colunas kk e ck.
A troca de linhas equivale a realizar uma pré-multiplicação da ma-
triz, ou seja,
I �A Ak lk
k k
, ·
� � � ��
Já a troca entre as colunas kk por ck pode ser calculada por meio de
uma pós-multiplicação calculada por
A I Ak k ck
k� � � ��· ,
Portanto,
A(k+1) = Mk · (Pk · A
(k) · Qk) (2)
Vamos acompanhar o exemplo a seguir para compreendermos melhor.
Exemρlo 7
Seja A �
�
�
�
�
�
�
�
�
�
�
1 2 3
4 5 6
7 8 9
, então P23
1 0 0
0 0 1
0 1 0
�
�
�
�
�
�
�
�
�
�
�
. Assim,
P A23
1 0 0
0 0 1
0 1 0
1 2 3
4 5 6
7 8 9
1 2 3
7 8 9
4 5 6
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�.
��
�
�
�
�
�
Considerando Q23
1 0 0
0 0 1
0 1 0
�
�
�
�
�
�
�
�
�
�
�
, escrevemos
AQ23
1 2 3
4 5 6
7 8 9
1 0 0
0 0 1
0 1 0
1 3 2
4 6 5
7 9 8
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�.
��
�
�
�
�
�
Sejam Qi, Pi e Mi as matrizes utilizadas até o passo k, a generalização
desse processo, fazendo-se a decomposição de A, com i = 1, ..., k, será:
A(k+1) = Mk · (Pk · ... · M2 · (P2 · M1 · (P1 · A
(1) · Q1) · Q2) · ... · Qk)
Sistemas de equações lineares 101
Agora, vamos considerar a matriz A = A(1) e efetuar todas as trocas
de linhas e colunas que foram aplicadas ao longo do processo até o
passo k, encontrando outra matriz A’:
A’(1) = Pk · ... · P1 · A
(1) · Q1 · ... · Qk
Aplicando o processo de Gauss em A’ e considerando que A’(i) são as
matrizes encontradas e M’i as matrizes elementares usadas, temos que:
A’(k+1) = M’k · ... · M’1 · A’
(1)
Algoritmo 4 – Decomposição de Gauss da matriz A com
pivoteamento completo
Para k = 1, 2, ..., r, queremos encontrar lk, ck ≥ k, tal que |alk,ck| =
max {|aij|, i, j ≥ k}. Se alk,ck = 0, faça r = k – 1, para
akj ↔ alk,j, j = k, ..., n
aik ↔ ai,ck, i = 1, ..., m
a m
a
a
i k mik ik
ik
kk
� � � �, ,...,1
a a m a i k m
j k n
ij ij ik kj� � � �
� �
. , ,...,
,...,
1
1
O processo para realizar o pivoteamento parcial é semelhante, po-
rém a diferença é que podemos realizar apenas a troca de linha (ou
coluna), se isso já for suficiente para obter o pivô desejado.
4.4 Condicionamento de sistemas lineares
Vídeo
Antes de tratarmos do condicionamento de sistemas de equações
lineares, vamos relembrar rapidamente os conceitos de norma de ve-
tores e matrizes.
4.4.1 Norma de vetores e matrizes
A análise do condicionamento de uma matriz depende do conceito
de norma de matriz, que, por sua vez, depende da norma de um vetor.
Assim, temos algumas definições que antecedem a construção da aná-
lise do condicionamento, como as elencadas a seguir.
102 Matemática para Computação
Definição 6
Norma de vetor é uma função
‖ · ‖: ℝn → ℝ
x ↦ ‖x‖
Satisfazendo:
• ‖x‖ ≥ 0, ∀ x ∈ ℝn;
• ‖x‖ = 0 ⇔ x = 0;
• ‖α · x‖ = |α| · ‖x‖, α ∈ ℝ;
• ‖x + y‖ ≤ ‖x‖ + ‖y‖.
Algumas das normas mais utilizadas, de acordo com Campos
Filho (2018), são:
I. Norma da soma de magnitudes:
x
1
1
�
�
� xi
i
n
II. Norma euclidiana:
x
2
2
1
�
�
�Xi
i
n
III. Norma do máximo ou norma infinita:
x max x
i n i�
� � �
� �1
O conceito de norma está relacionado geometricamente ao concei-
to de distância. Dessa maneira, é comum trabalharmos com a defini-
ção de distância entre pontos ou mesmo entre vetores. Veremos na
sequência mais algumas definições que trazem esses conceitos, para
que possamos aplicá-los no conceito de norma e distância de matrizes.
Definição 7
A distância entre dois pontos é dada pela expressão
d(x, y) = ‖x – y‖
para qualquer norma.
Sistemas de equações lineares 103
Após apresentarmos a distância entre vetores, podemos trazer a
definição de convergência, que considera como base as definições
8 e 9, as quais usam como eixo central a definição 7.
Definição 9
{x(k)} → x em relação à norma ‖ · ‖∞ ⇔ lim x x
k i
k
i
�
� � �
�
, i = 1, 2, ..., n.
Definição 8
{x(k)} → x em relação à norma ‖ · ‖, se para todo ε > 0 existe um N(ε), tal
que ‖x(k) – x‖ < ε,∀ k ≥ N (ε).
Concluímos que todas as normas vetoriais no ℝn são equivalentes à
convergência, ou seja, se {x(k)} → x em relação a uma norma ‖ · ‖, então
{x(k)} → x em relação a qualquer outra norma ‖ · ‖.
Quando se trata de matrizes, as relações são semelhantes.
Definição 10
A norma de uma matriz An é uma função
‖ · ‖: ℝnxn → ℝ
A ↦ ‖A‖
que satisfaz:
• ‖A‖ ≥ 0, ∀ A ∈ ℝnxn;
• ‖A‖ = 0 ⇔ A = 0 matriz nula;
• ‖α · A‖ = |α| · ‖A‖, α ∈ ℝ;
• ‖A + B‖ ≤ ‖A‖ + ‖B‖.
Podemos definir a distância entre matrizes, apesar de parecer um
conceito bastante estranho, da seguinte maneira: d(A, B) = ‖A – B‖.
Com isso, a norma de uma matriz é definida usando os conceitos
vistos anteriormente para as normas vetoriais, sendo que algumas nor-
mas matriciais costumam ser mais adotadas do que outras. Observe a
definição a seguir sobre uma dessas normas.
Definição 11
Se ‖ · ‖ é uma norma vetorial, então
A max A x max a
x i n ij
jn
�
�
�� � �� � �
�
�
1 1
1
é uma norma matricial, que se chama norma natural ou induzida.
104 Matemática para Computação
Normas induzidas (naturais) têm diversas vantagens, como:
• Seja x ≠ 0 e ‖ · ‖ uma norma natural ou induzida pela norma ve-
torial, então
‖Ax‖ ≤ ‖A‖ · ‖x‖
• ‖l‖ = 1;
• Raio espectral ρ(A) = max|λ|, em que λ é um autovalor de A.
Algumas das normas mais utilizadas são:
I. Norma 1:
A max A x max a |
x j n iji=1
n
1
1 1
1 1
� � �
� � �
�|
II. Norma euclidiana:
A max A x
x2 2 1
2
� � � �
�
�( )A AT
III. Norma do máximo ou norma infinita:
� � ��
� �
� ����� �����
A max A x max a |
x i n
máximo�d
ij
j=1
n
�
�
�� � �� � �
�
1 1
|
aa�soma�das�linhas
Com o conhecimento de algumas propriedades das normas de ve-
tores e de matrizes, podemos entrar no assunto condicionamento.
4.4.2 Número de condicionamento
Considere o sistema � .
1 1
1 2
10
5
1
2�
�
�
�
�
�
�
�
�
�
�
�
� � �
�
�
�
�
�
�
x
x
, cuja solução exata
é xexato �
�
�
�
�
�
�
5
5
.
Estamos fazendo uma pequena perturbação no sistema quando al-
teramos os elementos da matriz dos coeficientes ou do vetor indepen-
dente de maneira muito suave, ou seja, com uma pequena alteração.
Para esse sistema, vamos perturbar o vetor de termos independentes
b �
�
�
�
�
�
�
�
10
5
, para b1
10 01
5
�
�
�
�
�
�
�
�
, .
Sistemas de equações lineares 105
O sistema passa a ser 1 1
1 2
10 01
5
1
2�
�
�
�
�
�
� �
�
�
�
�
�
� � �
�
�
�
�
�
�
x
x
, , cuja solução é
x �
�
�
�
�
�
�
5 007
5 003
,
,
, sendo que x xexato≈ e o resíduo (r = Ax – b) é pequeno, pois
1 1
1 2
5 007
5 003
10
5�
�
�
�
�
�
� �
�
�
�
�
�
� � �
�
�
�
�
�
�
,
,
Agora, seja o sistema de equações representado por
1 1
1 001 1
10
10 005
1
2, ,
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
x
x
, cuja solução exata também é xexato �
�
�
�
�
�
�
5
5 ,
ao perturbarmos o vetor de termos independentes b, transformando-o
em b1
10
10 1
�
�
�
�
�
�
�,
, encontramos:
1 1
1 001 1
10
10 1
1
2, ,
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
x
x
cuja solução é x �
�
�
�
�
�
�
�
100
90
.
Se olharmos apenas para o resíduo, ou seja, para r = Ax – b, temos que
1 1
1 001 1
100
90
10
10 1, ,
�
�
�
�
�
� � �
�
�
�
�
�
� �
�
�
�
�
�
� � b
Contudo, percebemos que a solução se apresentou muito diferente
do que foi encontrado no primeiro sistema. Por isso, a pergunta que
fazemos é:
Por que uma perturbação de mesma ordem de grandeza interferiu tanto
em uma resposta, mas não na outra?
A resposta para esse problema está justamente no condicionamen-
to da matriz ou, mais especificamente, no número que representa esse
condicionamento.
Vamos supor que x resolve exatamente A · x = b, e x resolve aproxi-
madamente A · x = b, isto é, A · x ≈ b e r é o resíduo r = b – A · x .
Então,
x x
x
cond A r
b
�
� � � �
106 Matemática para Computação
Queremos analisar se ‖r‖ ≈ 0 implica ‖x – x ‖ ≈ 0. Para isso, assumi-
mos que r = b – A · x . Assim, desenvolvemos
r = Ax – A · x = A(x – x )
(x – x ) = A-1 · r
Mas,
‖x – x ‖ = ‖A-1 · r‖ ≤ ‖A-1‖ · ‖r‖
Pois estamos considerando uma norma induzida.
Portanto,
x x
x
A r
x
�
�
��1
Como 1
x
A
b
≤ , temos que:
x x
x
A r
A
b
�
� � ��1
Definindo cond(A) = ‖A-1‖ · ‖A‖, obtemos:
x x
x
cond A r
b
�
� � � �
ou
ER cond A ERx
Erro�relativo�em�x
b
Erro�relativo�e
��� �� ��� ��
� � � �
mm�b
O erro relativo em b é considerado porque r b Ax b b� � � � .
Com isso, mesmo que ‖r‖ ≈ 0, não implica x x� � 0 , a menos que
cond(A) também seja pequeno (CHAPRA, 2016).
Concluímos assim que, quanto maior é o cond(A), é mais provável
que o sistema seja sensível às mudanças em dados iniciais. Além disso,
definimos:
Definição 12
O número de condicionamento de uma matriz não singular A é
condp(A) = ‖A‖p · ‖A-1‖p
em que p é a norma adotada. Observe que o número de condicionamento
depende da norma escolhida.
Sistemas de equações lineares 107
A seguir, listamos as propriedades, considerando apenas normas
induzidas.
I. cond(A) ≥ 1
cond(A) = ‖A‖ · ‖A-1‖ ≥ ‖A · A-1‖ = ‖ I ‖ = 1
II. Se D é uma matriz diagonal, então cond D
d
d
ii
ii
� � � max
min
, indepen-
dentemente da norma escolhida. Por exemplo, na norma infinita:
D
d
d
dnn
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11
22
...
, D
d
d
dnn
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
11
22
1
1
1
...
D dii��max ,
D
d dii ii
� � �1
1 1
� max min
cond D
d
d
ii
ii
� � � max
min
III. cond(αA) = cond(A), ∀ α ∈ ℝ, α ≠ 0. Isso significa que, se uma ma-
triz for multiplicada por um escalar, seu número de condição não
mudará:
cond A A A A A cond A� �
�
�
�
� � � � � � � � � � � �� �1 11 1
IV. cond(A) = cond(A-1).
O exemplo a seguir nos ajudará a compreender algumas dessas
propriedades.
Exemρlo 8
Seja um sistema de equações Ax = b, no qual A �
�
�
�
�
�
�
�
�
0 992 0 873
0 481 0 421
, ,
, ,
,
assumimos que
A max A x max a
x i n ij
j
n
�
�
�� � �� � �
�
�
1 1
1
Lembre-se de que, para
facilitar esses cálculos, é
possível usar diversas fer-
ramentas computacionais.
Sugerimos a página do
Matrixcalc para o cálculo
da matriz inversa de A.
Disponível em: https://matrixcalc.
org/pt/#%7B%7B0%2e992,
-0%2e873%7D,%7B0%2e481,
-0%2e421%7D%
7D%5E%28-1%29.
Acesso em: 16 jul. 2021.
Já para aqueles que se
interessam por programa-
ção, enquadrando-se os
que estão iniciando nessa
área, sugerimos o Python.
Nesse caso, recomenda-
mos o código que consta
no Exemplo 8, que calcula
o condicionamento da
matriz A para a norma 1,
norma euclidiana e norma
infinita.
Código 1:
import numpy as np
A = np.array([[0.992,
-0.873],[0.481,-
0.421]],
dtype=’double’)
print(np.linalg.
cond(A,p=1))
print(np.linalg.
cond(A,p=2))
print(np.linalg.con-
d(A,p=np.inf))
Saiba mais
https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29
https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29
https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29
https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29
https://matrixcalc.org/pt/#%7B%7B0%2e992,-0%2e873%7D,%7B0%2e481,-0%2e421%7D%7D%5E%28-1%29
108 Matemática para Computação
Assim, temos que a norma infinita para A será
‖A‖∞ = max{(|0,992| + |-0,873|), (|0,481| + |-0,421|)} = 1,865
Como desejamos calcular o condicionamento de A, precisamos en-
contrar a matriz A–1 e, na sequência, encontrar ‖A-1‖∞. Para isso, fazemos
A� �
�
�
�
�
�
�1
421 000
2 281
873 000
2 281
481 000
2 281
992 000
2 281
.
.
.
.
.
.
.
.
��
�
�
�
�
�
�
�
Logo,
‖A-1‖∞ = max
.
.
.
.
, .
.
.
� �
�
�
�
�
�
� � �
421 000
2 281
873 000
2 281
481 000
2 281
992 000
2..281
�
�
�
�
�
�
�
�
�
��
�
�
�
��
= 645,77
Com isso, o condicionamento de A será
cond(A) = ‖A-1‖ · ‖A‖ = 1,865 · 645,77 = 1.204,36
Portanto, o condicionamento de uma matriz pode ser analisado
para compreendermos o comportamento do sistema de equações a
ser resolvido. Além disso, podemos usar o condicionamento para ana-
lisar a matriz dos coeficientes e, com isso, escolher o método mais ade-
quado para a resolução do sistema.
4.5 Métodos iterativos
Vídeo Um método iterativo é aquele que usa informações de, no mínimo,
um passo anterior para resolver o seguinte, sendo de grande impor-
tância na solução de problemas que envolvem matrizes esparsas de
grande porte no caso dos sistemas de equações.
Uma matriz esparsa tem como característica um grande número
de elementos iguais; em geral, esse elemento repetido é o elemento
neutro. São também consideradas matrizes esparsas aquelas com ele-
mentos faltantes. Isso é comum quando essa matriz foi alimentada, por
exemplo, por uma pesquisa que possuía dados incompletos de seus
participantes. Essas matrizes tambémsão comuns no estudo da teoria
dos grafos e na resolução de equações diferenciais. A seguir, definimos
o formato dos métodos iterativos.
Sistemas de equações lineares 109
Definição 13
Seja A ∈ ℝn⨯n esparsa e de grande porte, tal que Ax = b, os métodos itera-
tivos têm o formato geral:
A = N – P (3)
Assim,
N · x – P · x = b
N · x = P · x + b = b
tal que N · x = b seja mais fácil de ser resolvido do que A · x = b.
O processo iterativo é definido por
N · x(k+1) = P · x(k) + b, k = 0, 1 (4)
com x(0) dado.
Portanto,
x(k+1) = N–1 · P · x(k) + N–1 · b (5)
Se a sequência gerada {x(k)} converge para x* quando k → ∞, então
N · x* = P · x* + b converge para Ax* = b, isto é, x* é a solução do sistema.
Partindo desse processo principal, temos uma questão importante
que diferencia os métodos iterativos: a escolha da matriz N.
Assim, os métodos que serão tratados na sequência se diferenciam
justamente por essa matriz. Vamos entendê-los.
4.5.1 Método de Gauss-Jacobi
Como comentamos anteriormente, a escolha de N define diferentes
métodos iterativos. O primeiro método que estudaremos é conhecido
como método de Gauss-Jacobi ou simplesmente método de Jacobi.
4.5.1.1 Escolha de N
No método de Jacobi, a matriz N será uma matriz diagonal, ou seja,
N
a
a
ann
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11
22
0 0
0 0
0 0
...
...
... ... ... ...
...
O matemático alemão
Carl Gustav Jakob Jacobi
(1804 – 1851) deixou
importantes contribuições
nas mais diversas áreas
da Matemática. Dentre
elas, encontramos a
matriz Jacobiana, impor-
tante para a resolução
de problemas de cálculo
avançado. Também é
ele quem referenciamos
quando trabalhamos com
o método para solução
de sistemas de equações
iterativo que assume a
matriz N como uma ma-
triz diagonal. Para saber
mais sobre Jacobi e suas
contribuições, sugerimos
o material disponível no
Instituto Superior Técnico.
Disponível em: http://e-escola.
tecnico.ulisboa.pt/personalidade/
jacobi-carl-gustav-jakob. Acesso em:
16 jul. 2021.
Saiba mais
http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob
http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob
http://e-escola.tecnico.ulisboa.pt/personalidade/jacobi-carl-gustav-jakob
110 Matemática para Computação
Pela equação (3), temos:
P N A
a a
a a
a a
n
n
n n
� � �
� �
� �
� �
�
�
�
�
0
0
0
12 1
21 2
1 2
...
...
... ... ... ...
...
��
�
�
�
�
�
�
�
�
�
Portanto, fazendo N · x = P · x + b, obtemos
a
a
a
x
x
xnn
11
22
1
2
0 0
0 0
0 0
...
...
... ... ... ...
...
...
�
�
�
�
�
�
�
�
�
�
�
�
�
� nn
n
n
n
a a
a a
a
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
� �
0
0
12 1
21 2
1
...
...
... ... ... ...
aa
x
x
x
b
b
bn n n2
1
2
1
2
0...
.
... ...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
Se aii ≠ 0 para todo i, então x� � N �P �x� � N �b
T c
� � �� �1 1� �� �� � �� �� , o que nos leva
à seguinte equação
x = Tx + c (6)
que tem como representação matricial:
x
x
x
a
a
a
a
a
a
a
a
n
n
n
1
2
12
11
1
11
21
22
2
0
0
...
...
...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
� �
222
1 2
1
0
... ... ... ...
...
.
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
a
a
a
a
x
n
nn
n
nn
xx
x
b
a
b
a
b
a
n
n
nn
2
1
11
2
22...
...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
As equações de iteração são obtidas quando isolamos, em cada
equação do sistema, uma variável de cada vez. Assim,
x
a
b a x � a x
x a
b
k k
n n
k
k
1
1
11
1 12 2 1
2
1
22
2
1
1
�� � � � � �
�� �
� � � ��
�
�
�
�
�
�
�
...
aa x a x
x
a
b a x a
k
n n
k
n
k
nn
n n
k
21 1 2
1
1 1
1
� � � �
�� � � �
� ��
�
�
�
�
�
� � � �
...
...
nn n n
kx �, � �
� ��
�
�
�
�
�1 1
Veremos a interpretação gráfica do método na Figura 5.
Sistemas de equações lineares 111
4.5.1.2 Interpretação gráfica do método
Para apresentarmos a interpretação gráfica, vamos assumir que o
sistema de equações é composto por duas equações e duas incógnitas.
Para esse tópico, assumiremos alguns valores específicos para o siste-
ma de equações de modo que possamos garantir uma representação
gráfica consistente.
Assim, seja Ax = b dado por duas retas r1 e r2, tais que
r �x y
r x y
1
2
5
2 8
:
:
� �
� �
�
�
�
��
,
assumiremos que x 0
1
2
1
2
� � � �
�
�
�
�
�, . O gráfico com a intersecção entre essas
duas retas, também compreendida como a solução do sistema de
equações, será:
Figura 5
Representação do sistema r �x y
r x y
1
2
5
2 8
:
:
� �
� �
�
�
�
y
–0,5–1,5–2,5–3,5–4,5–5,5 –1–2
–2
–1,5
–0,5
0,5
0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,51 2 3 4 5 6 7 8
r1 : x + y = 5
r2 : x + 2y = 8
A = (2,3)
x(0)
x(1)
9
1
1,5
2
2,5
3
3,5
4
4,5
5
5,5
6
–1
–3–4–5–6 0 x
G
J
H
I
Fonte: Elaborada pela autora.
112 Matemática para Computação
Para verificar se o método converge para a solução do sistema,
fazemos:
x x
x x
k k
k k
1
1
2
2
1
1
5
4 1
2
�� � � �
�� � � �
� �
� �
�
�
�
�
�
Assumindo, assim,
x 0
1
2
1
2
� � �
�
�
�
�
�
�
�
�
�
�
�
�
A próxima etapa é calcular x(1). Portanto,
x
x
1
1
2
1
5 1
2
9
2
4 1
2
1
2
15
4
� �
� �
� � �
� �
�
�
�
�
�
� �
�
�
��
�
�
�
Logo,
x �x �*1
9
2
15
4
2
3
� � �
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
Portanto, o método converge para a solução do sistema.
4.5.1.3 Convergência do método
Quando citamos métodos numéricos iterativos, sempre menciona-
mos a convergência do método. Para o método de Jacobi, seja qualquer
x(0) inicial, ou seja, ponto de partida, a sequência {x(k)} ficará definida por
x(k+1) = T · x(k) + c
Portanto, {x(k)} converge para uma única solução x, tal que
x = T · x + c ⇔ ρ(T) <1
ou
‖T‖ < 1 ⇒ {x(k)} → x
em que Ax = b para qualquer x(0).
Sistemas de equações lineares 113
De acordo com Dornelles Filho (2016, p. 67), que valida o trabalho
de Burden e Faires (2015), “o primeiro critério é necessário e suficiente,
porém computacionalmente trabalhoso de ser verificado. O segundo
critério é suficiente, mas não necessário, porém mais facilmente verifi-
cável”. Usando a norma infinita, temos:
T
a
a
a
a
a
a
a
a
a
a
n
n
n
nn
�
� �
� �
� �
0
0
12
11
1
11
21
22
2
22
1
...
...
... ... ... ...
aa
a
T
n
nn
2 0
1
...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � (max soma das linhas)
Portanto,
a
a
ij
iij
j i
n
�
�
� �
1
1,
para todo i, tal que
a a � �iii ij
n
� �
�
�
� ,
j
j i
1
o que equivale a afirmar que A é diagonalmente dominante.
Algoritmo 5 – Gauss-Jacobi
• Passo 1: entrada: A, b, �, N, x(0)
• Passo 2: k = 0
• Passo 3: para i = 1, 2, ..., n
x
a
b a x a xi
k
ii
i ij
j
i
j
k
ij
j i+1
n
j
k�� �
�
�
� �
�
� �� � � � �
�
�
�
��
�
�
�
��
� �1
1
1
1
• Passo 4: se x x �i 1, ..., ni
k
i
k�� � � �� � �1 � , ou k > N, então x = x(k+1).
Se não, k = k + 1, voltar para passo 3.
O exemplo a seguir faz uma aplicação do algoritmo do método
de Jacobi.
114 Matemática para Computação
Exemplo 9
Vamos organizar a primeira iteração que permite resolver pelo mé-
todo de Jacobi o sistema de equações Ax = b, com
A �x
x
x
x
�e�b� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
10 2 1
0 5 2
1 2 20
20
20
20
1
2
3
, ���
�
�
�
�
�
�
�
Calculando as matrizes P, N-1 e T, temos
P �
� �
�
� �
�
�
�
�
�
�
�
�
�
�
0 2 1
0 0 2
1 2 0
, N� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
10
0 0
0 1
5
0
0 0 1
20
e �T �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0 1
5
1
10
0 0 2
5
1
20
1
10
0
.
Podemos notar que a matriz A � �
�
�
�
�
�
�
�
�
�
�
�
10 2 1
0 5 2
1 2 20
é diagonalmente
dominante, pois ‖T‖ < 1.
Consideraremos x 0
0
0
0
� � �
�
�
�
�
�
�
�
�
�
�
. Assim,
x b x x
x b x x
k k k
k k k
1
1
1 2 3
2
1
2 1 3
1
10
2
1
5
0 2
�� � � � � �
�� � � � �
� � ��
�
�
�
�
�
�
�
�� ��
�� � � � � �
�
�
�
�
�
�
�
�
� ��
�
�
�
�
�x b x x
k k k
3
1
3 1 2
1
20
2
A ordem de convergência e a taxa de convergência também podem
ser avaliadas. Lembrando que esses valores são descritos por inter-
médio da análise da aproximação da solução numérica em relação à
solução exata por meio da expressão
lim
x x
C
k
k
p
Ordem�de�convergência
Taxa�de�conv
�
�� � �
�
�
�
1
x xk( )
eergência
Sistemas de equações lineares 115
Desse modo, teremos p = 1. Temos, portanto, uma convergência
linear e
lim
x x
x x
T
k
k
k p�
�� �
� �
�
�
�
�
1
, pois
x � �x T x ��xk k�� � � �� � � �� �1
Sendo assim,
lim
x x
x x
T
k
k
k�
�� �
� �
�
�
�
�
1
1
Desse modo, além de conseguirmos resolver um sistema de equações
por métodos chamados de iterativos, é possível avaliarmos a convergência
do método, fato esse que é imprescindível para uma boa análise numérica
sobre a aplicação de qualquer tipo de método numérico.
4.5.2 Método de Gauss-Seidel
Assim como no método de Jacobi, a escolha da matriz N define os
passos a seguir. Portanto, para definirmos o método de Gauss-Seidel,
em primeiro lugar tratamos da matriz N.
4.5.2.1 Escolha de N
No método iterativo de Gauss-Seidel, a escolha da matriz N se dá
por uma matriz triangular inferior na forma
N
a
a a
a a an n nn
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11
21 22
1 2
0 0
0
...
...
... ... ... ...
...
Com isso, teremos
P N A
a a
a
n
n� � �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0
0 0
0 0 0
12 1
2
...
...
... ... ... ...
... ��
116 Matemática para Computação
Portanto, assumindo N · x = P · x + b, obtemos
a
a a
a a a
x
n n nn
11
21 22
1 2
10 0
0
...
...
... ... ... ...
...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
xx
x
a a
a
n
n
n2
12 1
2
0
0 0
0 0
...
...
...
... ... ... ...
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
....
.
... ...
0
1
2
1
2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
x
x
x
b
b
bn n
��
�
�
�
�
�
�
�
�
E podemos escrever
x
a
b a x a x
x
a
b a
k k
n n
k
k
1
1
11
1 12 2 1
2
1
22
2
1
1
�� � � � � �
�� �
� � � ��
�
�
�
�
�
� �
...
221 1
1
2
1
1 1
11
x a x
x
a
b a x
k
n n
k
n
k
nn
n n
k
�� � � �
�� � �� �
� ��
�
�
�
�
�
� � �
...
.
... ,�
�
�
�
�
�
�� �
�� �a xn n n
k
1 1
1
Note que, x k1
1�� � é calculado apenas com termos no passo x(k). Os
demais valores para xi, com i = 2, …, n, além de utilizarem valores no
passo k, também usam valores no passo k + 1 para os xi elementos,
com xi = 1, …, n – 1.
4.5.2.2 Interpretação gráfica do método
Para apresentarmos a interpretação gráfica, adotaremos o mesmo
princípio usado no método de Gauss-Jacobi e o mesmo sistema de
equações lineares.
Assim, seja Ax = b dado por duas retas r1 e r2, tais que
r �x y
r x y
1
2
5
2 8
:
:
� �
� �
�
�
�
��
.
Assumiremos x 0 1
2
1
2
� � � �
�
�
�
�
�, .
A seguir, apresentamos o gráfico que mostra a intersecção entre
essas duas retas, também compreendida como a solução do sistema
de equações.
Sistemas de equações lineares 117
Figura 6
Sistema de equações r �x y
r x y
1
2
5
2 8
:
:
� �
� �
�
�
�
y
–0,5–1,5–2,5–3,5–4,5–5,5 –1–2
–2
–3
–1,5
–2,5
–0,5
0,5
0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 8,5 9,5 101 2 3 4 5 6 7 8
r1 : x + y = 5
r2 : x + 2y = 8
A = (2,3)
x(0)
x(1)
9
1
1,5
2
2,5
3
3,5
4
4,5
5
6
5,5
–1
–3–4–5–6 0
x
G
H
JI
Fonte: Elaborada pela autora.
Para verificarmos se o método converge para a solução do sistema,
fazemos:
x x
x x
k k
k k
1
1
2
2
1
1
1
5
4 1
2
�� � � �
�� � �� �
� �
� �
�
�
�
�
�
Assumindo, então,
x 0
1
2
1
2
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
118 Matemática para Computação
A próxima etapa é calcular x(1). Portanto,
x
x
1
1
2
1
5 1
2
9
2
4 1
2
9
2
7
4
� �
� �
� � �
� �
�
�
�
�
�
� �
�
�
��
�
�
�
Logo,
x x*1
9
2
7
4
2
3
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
Assim, o método converge para a solução do sistema.
4.5.2.3 Convergência do método
De acordo com Chapra (2016), temos que as condições para a con-
vergência do método coincidem com as condições já vistas no método
de Jacobi, ou seja, ρ(T) ≤ 1, em que T = N-1 · P.
Além da verificação por meio do raio espectral, podemos usar uma
condição suficiente, conhecida por critério de Sassenfeld, como expressam
Burden e Fraires (2015).
De acordo com esses dois autores, precisamos calcular βj, com j = 1,
2, ..., n em que
�1
12 13 1
11
1�
� � �
�
a a a
a
n...
�
� �
j
j j j j j j jn
jj
a a a a
a
j n�
� � � � � � �
� �
� � �1 1 1 1 1 1 2
... ...
, ,...,, ,
Se β = max1≤j≤n, βj < 1, então o método de Gauss-Seidel converge para
x independente de x(0), isto é, {x(k)} → x.
A ordem de convergência, assim como no método de Jacobi, é li-
near, e a taxa de convergência será igual a β, sendo que, quanto menor
seu valor, mais rápida será a convergência. O exemplo a seguir esclare-
ce esses conceitos.
Sistemas de equações lineares 119
Exemρlo 10
Seja A �
�
�
�
�
�
�
�
�
�
�
8 2 1
5 4 1
4 3 4
uma matriz não diagonalmente dominante, note
que ρ(T) ≤ 1, pois os autovalores de T são λ1 = 0, λ2 = 0,2983 e λ3 = 0,2095.
Portanto, podemos usar o critério de Sassenfeld. Assim, obtemos
�1
2 1
8
1� � �
�
�
2
15 1
4
23
32
1�
� �
� �
�
� �
3
1 24 3
4
117
128
1�
� � �
� �
Nesse caso, como βi < 1 para i = 1, 2, 3, podemos aplicar qualquer
um dos métodos iterativos vistos anteriormente (Gauss-Jacobi ou
Gauss-Seidel).
O que podemos afirmar sobre a relação entre os critérios de linha
e de Sassenfeld?
Se o critério de linhas for satisfeito, então o critério de Sassenfeld tam-
bém será.
Se o critério de Sassenfeld não for satisfeito, o critério de linhas também
não será.
Resumidamente:
CL⇒ CS e não CS ⇒ não CL
Por intermédio da análise do critério de Sassenfeld para o método
de Gauss-Seidel, notamos que o método gera uma sequência conver-
gente. Assim, se
‖x(k+1) – x‖ ≤ β ‖x(k) – x‖, ∀ k
120 Matemática para Computação
Então,
lim
k
k
k Ordem�de�convergência
Taxa�de�co
x x
x x
�
�� �
� � �
�
�
�
�
�
1
1 ���
nnvergência
Observação: a taxa de convergência é menor do que a taxa do mé-
todo de Gauss-Jacobi, pois:
a a a a
a
a a ak k k k k k kn
kk
k k k k1 1 1 1 1 1 1� � � � � � � �
� � �� � � �� �... ... ..., , , ,, ... ,k kn
kk
a
a
�k�
� �
�1
a a a a
a
max
a ak k k k k k kn
kk k
k k k1 1 1 1 1 1� � � � � � � �
� �� � � �� �... ... ..., , , 11 1� � ��
�
�
��
�
�
�
��
� ��
a a
a
T kk k kn
kk
, .... ,
βk < ‖T‖, ∀ k
Então, maxβk < ‖T‖.
Logo,
�
��� ���
Taxa�de�Gauss Seidel Taxa�de�Gauss Jacobi
T
� �
�
Algoritmo 6 – Gauss-Seidel
• Passo 1: entrada: A, b, �, N, x(0).
• Passo 2: k = 0.
• Passo 3: para i = 1, 2, ..., n
x
a
b a x a xi
k
ii
i ij
j
i
j
k
ij
j
j
k�� �
�
�
�� �
� �
� �� � � � �
�
�
�
��
�
�
�� �1
1
1
1
1
1
i
n
���
• Passo 4: se x x �para�i ni
k
i
k�� � � �� � �1 1� , ,..., , ou k > N, então x =
x(k+1). Se não, k = k + 1, voltar para o passo 3.
Vamos acompanhar o exemplo a seguir, no qual utilizamos o algo-
ritmo de Gauss-Seidel.
Sistemas de equações lineares 121
Exemρlo 11
Seja a matriz A dada por A � �
�
�
�
�
�
�
�
�
�
�
�
10 2 1
0 5 2
1 2 20
, resolva, utilizando o
método de Gauss-Seidel, o sistema de equações dado por Ax �
�
�
�
�
�
�
�
�
�
�
20
20
20
,
considerando x 0
0
0
0
� � �
�
�
�
�
�
�
�
�
�
�
.
Para isso, fazemos
x x x
x x x
k k k
k k
1
1
2 3
2
1
1
1
3
1
10
20 2
1
5
20 0 2
�� � � � � �
�� � �� �
� � ��
�
�
�
�
�
�
�
� � kk
k k kx x x
� �
�� � �� � �� �
�
�
�
�
�
�
�
�
� ��
�
�
�
�
�3
1
1
1
2
11
20
20 2
Devemos notar que cada método se adapta melhor a um tipo de sis-
tema ou situação aplicada. Os métodos podem ser comparados, com
isso, geram uma análise mais profunda dos resultados obtidos.
Compare os métodos
e faça a análise dos
resultados.
Desafio
CONSIDERAÇÕES FINAIS
Com este capítulo foi possívelrevermos alguns conceitos estudados
nos ensinos médio e fundamental, além de aprendermos algumas teorias
ainda não trabalhadas nos ensinos de base.
Temos com isso várias estratégias para a resolução de sistemas de
equações lineares vinculados diretamente ao conceito de matrizes e
transformados em algoritmos, para conseguirmos pensar em estratégias
computacionais de programação para tais métodos.
A intenção é munir você de ferramentas que serão extremamente
úteis não só no que se refere à resolução de problemas, mas em muitas
outras situações, de maneira teórica e aplicada.
Também indicamos que você acesse aos links sugeridos como comple-
mentação ao conteúdo e resolva o máximo de exercícios possíveis sobre
o tema. Acreditamos que o tripé teoria, prática e aplicação é necessário
para a boa compreensão de qualquer conceito.
122 Matemática para Computação
ATIVIDADES
Seja A a matriz dos coeficientes de um sistema de equações lineares
do tipo Ax = b, por que precisamos ter det ≠ 0 para garantir a inversão
dessa matriz? Explique.
Atividade 1
Um sistema de equações lineares pode ter como solução infinitas solu-
ções. Isso é válido para o sistema a seguir? Justifique.
x y z
x y z
x y z
� � �
� � �
� � � � �
�
�
�
�
�
1
2 2 2 2
1
Atividade 2
Explique, com suas palavras, o que significa a análise de convergência
de um método e qual é a sua importância para garantir o resultado
encontrado.
Atividade 3
REFERÊNCIAS
BURDEN, R. L.; FAIRES, J. D. Análise numérica. São Paulo: Cengage Learning, 2015.
CAMPOS FILHO, F. F. Algoritmos numéricos: uma abordagem numérica de cálculo numérico.
Rio de Janeiro: LTC, 2018.
CHAPRA, S. C.; CANALE, R. P. Métodos numéricos para engenharia. 7. ed. Porto Alegre:
AMGH, 2016.
DORNELLES FILHO, A. A. Fundamentos de cálculo numérico. São Paulo: Bookman, 2016.
LEON, S. J. Álgebra linear com aplicações. 9. ed. Rio de Janeiro: Livros Técnicos e Científicos, 2019.
Grafos e árvores 123
5
Grafos e árvores
O primeiro teorema desenvolvido na teoria dos grafos é atribuído ao
matemático Leonhard Euler. Isso ocorreu no ano de 1736. Euler desen-
volveu um modelo que permitia encontrar um caminho passando pe-
las sete pontes da cidade de Königsberg, antiga Prússia, hoje chamada
Kaliningrado, na atual Rússia.
Mas não era um caminho qualquer. Uma vez que se passasse por
determinado trecho para chegar em uma das pontes, aquele caminho
precisava ser retirado do modelo e, assim, não era possível passar duas
vezes pelo mesmo trecho do caminho.
Euler trabalhou sobre esse modelo assumindo algumas simplificações
das ligações entre as regiões e desenvolveu um teorema que estabelece
em que condições é possível percorrer cada trecho (linha) exatamente
uma vez e voltar ao ponto inicial.
Esse tipo de modelo, hoje em dia, é usado por empresas como Amazon,
Uber e Correios, que dependem, por exemplo, de rapidez no transporte
de mercadorias. Mas não é só o transporte de produtos que se beneficia
desses conceitos. Facebook, Google e outras gigantes da tecnologia tam-
bém usam a teoria dos grafos para o transporte de informações.
Vamos ver, ao longo do texto, a teoria e as aplicações do conceito de
grafos e a importância dessa grande área do conhecimento, que por si só
renderia uma obra inteira.
Com o estudo deste capítulo, você será capaz de:
• conhecer um pouco a história dos grafos, suas terminologias e
seus tipos;
• vincular o conceito de grafos e árvores aos conceitos de funções;
• aplicar a formulação matricial ou vetorial ao conceito de grafo
por meio dos caminhos entre vértices e arestas;
• compreender o conceito de árvore como subgrupo dos grafos;
• identificar alguns algoritmos de busca representados por grafos
ou árvores.
Objetivos de aprendizagem
5.1 O que é um grafo: terminologia e tipos
Vídeo A teoria dos grafos, que teve início com um modelo desenvolvido
por Euler em 1736, é hoje a base de diversas estruturas matemáticas e
computacionais, como as redes neurais, a criação de fluxogramas, as
redes de comunicação, os modelos de fluxo de dados, os algoritmos de
escalonamento e de pesquisa e ordenação, o layout de circuitos e os
modelos de máquinas de estado.
Ha
ha
m
h
an
uk
a~
co
m
m
on
sw
ik
i/W
ik
im
ed
ia
C
om
m
on
s Leonhard Paul Euler é um dos grandes nomes
da matemática e da física, mas acabou exercendo
influência em muitas outras áreas, inclusive na mú-
sica. Nascido na Basileia, Suíça, em 1707, passou a
maior parte de sua vida na Rússia e na Alemanha e
faleceu em São Petersburgo, Rússia, em 1783.
O problema modelado por Euler é conhecido
como o problema das sete pontes de Königsberg e con-
siste em um algoritmo que permite passar pelas sete
pontes dessa cidade, hoje chamada Kaliningrado, na
Rússia, sem passar pelos caminhos já percorridos.
Na sequência de figuras a seguir, é possível acom-
panhar o modelo usado nessa construção.
A Figura 1 mostra um pedaço do Rio Prególia,
onde ao fundo conseguimos observar uma das pon-
tes. Na época de Euler, as duas grandes ilhas localiza-
das nessa extensão do rio formavam um importante
complexo interligado por 7 pontes.
124 Matemática para ComputaçãoMatemática para Computação
Figura 1
Modelo real
Gumerov Ildar/Wikimedia Commons
Grafos e árvores 125
A Figura 2 foi idealizada para a comemoração dos 600 anos da fa-
mília real. Seu desenho está embasado em uma gravura de Joachim
Bering (1613) e data de aproximadamente 1813.
Figura 2
Modelo físico
M
er
ia
n-
Er
be
n/
W
ik
im
ed
ia
C
om
m
on
s
A imagem original não apresenta as marcações destacadas sobre as pontes e sobre o Rio Prególia.
Por fim, a Figura 3 apresenta o modelo matemático proposto por
Euler, que permitia a conexão entre as diferentes regiões do complexo
formado pelo rio, as ilhas e as sete pontes.
Figura 3
Modelo matemático
Nu
x/
W
ik
im
ed
ia
C
om
m
on
s
126 Matemática para Computação
Esse modelo foi idealizado em 1736, portanto, muitas mudanças
ocorreram ao longo dos anos, sendo que uma delas foi a derrubada de
algumas das pontes.
A Figura 4, a seguir, apresenta a vista por satélite da cidade de
Kaliningrado no ano de 2021.
Figura 4
Visualização de Kaliningrado por satélite
Fonte: Google Earth, 2021.
A teoria dos grafos é bastante extensa e precisaríamos de pelo menos
uma obra inteira para discutirmos sobre ela em todos os seus detalhes.
Mas traremos as características mais importantes quando pensamos em
possibilidades de transcrição de grafos e árvores para algoritmos, vincu-
lando esses conceitos às funções, aos vetores e às matrizes.
A estrutura de um grafo está diretamente relacionada às funções e às
matrizes. De maneira não formal, podemos afirmar que um grafo é um
par (ou um trio) de conjuntos. Formalmente temos a seguinte definição:
Definição 1
Um grafo é um objeto matemático (ou uma estrutura matemática) formado por
dois conjuntos. O primeiro deles, que denotaremos por V, é o conjunto de vérti-
ces. O segundo é o conjunto que relaciona os vértices (BOAVENTURA NETTO;
JURKIEWICZ, 2017).
Grafos e árvores 127
As relações entre vértices são chamadas de arestas. Portanto, o se-
gundo conjunto, denotado por A, é o conjunto de arestas. Assim, o gra-
fo é denotado por G = (V, A).
Por sua vez, o conjunto de arestas A, que relaciona dois vértices –
v e w –, tem elementos denotados por (v, w), sendo que v, w ∈ V. Com isso,
temos que os elementos do conjunto de arestas são pares ordenados.
Alguns autores referem-se aos vértices como nós. Portanto, qual-
quer uma das nomenclaturas pode ser usada de acordo com a aplica-
ção e a área em que o grafo está inserido.
Exemρlo 1
Determine os conjuntos de vértices e arestas do grafo representa-
do na Figura 5.
Figura 5
Grafo com quatro nós e cinco arestas
Fonte: Elaborada pela autora.
1
4
2
3
Observando a figura, identificamos os quatro vértices (nós) demar-
cados com a numeração de 1 a 4. Além disso, conseguimos descrever
as arestas que interligam alguns desses nós. Usando a notação defini-da anteriormente, escrevemos:
• G = (V, A)
• V = {1, 2, 3, 4}
• A = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}
128 Matemática para Computação
O número de vértices é representado por n = |V|. Logo, para o
Exemplo 1, temos n = 4. Já o número de arestas é representado por
a = |A|, observe que no grafo da Figura 5 temos a = 5.
Esse é um exemplo de grafo não orientado (não dirigido, não di-
recionado). Essa estrutura matemática pode ser vista em muitas si-
tuações aplicadas.
Um circuito eletrônico é formado por componentes e placas, mas,
em geral, o que desejamos saber é o caminho percorrido pela corrente
elétrica que passa por esses componentes.
Sistemas eletrônicos ou sistemas digitais funcionam por meio da
abertura e do fechamento de chaves lógicas (portas lógicas), sendo que
o fechamento permite que a energia passe pelo sistema, e a abertura
faz com que a energia seja cortada. Essas duas variáveis são represen-
tadas matematicamente por 0 e 1, o que é conhecido como sistema
binário (ou base binária).
As portas lógicas são formadas com base em transistores, mosfets e
resistores e cada uma realizará uma operação lógica diferente, tendo
também uma simbologia padrão relacionada. As Figuras 6 e 7 mostram
um pouco dessa simbologia.
Figura 6
Porta lógica AND
Fonte: Elaborada pela autora.
A
B
Xe
Figura 7
Porta lógica OR
Fonte: Elaborada pela autora.
A
B
Xou
A junção de diferentes portas lógicas está representada na Figura 8.
Figura 8
Portas lógicas
Fonte: Elaborada pela autora.
A
B
C
X
e
You
Para saber mais sobre
circuitos e sistemas
eletrônicos, indicamos as
seguintes leituras:
Organização estrutura-
da de computador, que
esclarece essa teoria com
o auxílio de imagens e re-
sume algumas seções da
obra Organização Estrutu-
rada de Computadores de
Andrew S. Tanenbaum.
Disponível em: http://www.dpi.
inpe.br/~carlos/Academicos/
Cursos/ArqComp/aula_5bn1.html.
Acesso em: 24 ago. 2021.
Na Apostila de teoria para
circuitos digitais, escrita
por Alexandre Santos
de la Vega, você saberá
mais sobre a teoria para
circuitos eletrônicos
Disponível em: http://www.
telecom.uff.br/~delavega/public/
CircDig/apostila_teo_cd.pdf.
Acesso em: 24 ago. 2021.
Leitura
http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html
http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html
http://www.dpi.inpe.br/~carlos/Academicos/Cursos/ArqComp/aula_5bn1.html
http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf
http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf
http://www.telecom.uff.br/~delavega/public/CircDig/apostila_teo_cd.pdf
Grafos e árvores 129
Apesar de esse tipo de sistema parecer bastante complexo, pode-
mos simplificá-lo usando vértices e arestas, já que o que desejamos
entender é o percurso realizado pela corrente elétrica.
Figura 9
Circuito eletrônico x grafo
Esquema
1
3
Grafo
5
42
3
5
42
1
Fonte: Adaptado de Goldbarg; Goldbarg, 2012.
Quando conhecemos a direção das arestas, ou seja, o caminho impos-
to entre um vértice e outro, temos um vetor que nos orienta sobre qual
é o vértice de partida e qual é o vértice de chegada. Nesse caso, o grafo
formado por esses vértices e essas arestas é chamado de grafo dirigido (ou
digrafo).
As Figuras 10 e 11, a seguir, mostram exemplos de grafos digrafos.
Figura 10
Grafo dirigido com quatro nós e cinco arestas
Figura 11
Digrafo composto por 20 nós e 20 arestas
Fonte: Elaborada pela autora.
1
4
2
3
al
ri/
Sh
ut
te
rs
to
ck
Note que, no grafo da Figura 10, temos os mesmos vértices do grafo
da Figura 5, porém agora as arestas estão orientadas. Dessa maneira,
escrevemos o conjunto de arestas como:
A = {(1, 2), (2, 3), (3, 2), (4, 2), (3, 1), (4, 3)}
Podemos associar a cada aresta uma função. Nesse caso, teremos
uma tripla ordenada da forma G = (V, A, f), em que f é uma função,
O material Uma introdução
sucinta à teoria dos grafos,
dos professores Feofiloff,
Kohayakawa e Wakabayashi,
apresenta de maneira bas-
tante didática e acessível
a estrutura conceitual e
alguns exemplos sobre
a teoria dos grafos. É um
material bem completo
que pode ser usado como
complemento de nosso
material.
Disponível em: https://www.ime.
usp.br/~pf/teoriadosgrafos/texto/
TeoriaDosGrafos.pdf. Acesso em: 24
ago. 2021.
Leitura
https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf
https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf
https://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf
130 Matemática para Computação
f: A → P (V), que associa a cada aresta um subconjunto de dois ou de
um elemento de V, interpretado como os pontos terminais da aresta.
Em um grafo ou digrafo com pesos, uma função adicional A → ℝ
associa um valor a cada aresta, o que pode ser considerado como seu
“custo”. O exemplo a seguir esclarece esses conceitos.
Exemρlo 2
Considere o grafo representado na Figura 12 a seguir. Determine o
número e o conjunto de vértices e arestas desse grafo.
Figura 12
Grafo com custos nas arestas
al
ri/
Sh
ut
te
rs
to
ck
Note que esse grafo apresenta valores em suas arestas, portanto,
identificamos que esses valores podem ser descritos por uma função
custo, como definido anteriormente.
Na sequência, apresentamos o conjunto de vértices, sendo n o nú-
mero de elementos desse conjunto, e, então, o número de vértices.
• V = {A, B, C, D, E, F}
• n = 6
Após essa etapa, montamos o conjunto de arestas, que leva em
consideração o sentido de cada uma delas. O valor a = 9 representa
o número de elementos desse conjunto, logo, é o número de arestas.
A = {(A, B), (A, D), (B, C), (B, E), (C, E), (C, F), (D, C), (D, E), (E, F)}
Podemos analisar a adjacência entre vértices por meio da conexão
entre arestas. A definição para esse conceito é apresentada a seguir.
Existem diversos tipos
de grafos: completos,
regulares, nulos, entre
outros. Para saber mais
sobre esse assunto e
poder escolher qual o
melhor tipo de grafo para
determinada representa-
ção, sugerimos o material
Grafos e algoritmos, de
Filipe Chagas.
Disponível em: https://medium.
com/@filipe.chagas/os-grafos-
e-os-algoritmos-697c1fd4a416.
Acesso em: 24 ago. 2021.
Saiba mais
https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416
https://medium.com/@filipe.chagas/os-grafos-e-os-algoritmos-697c1fd4a416
Grafos e árvores 131
Definição 2
Se um vértice v do grafo G é um dos extremos de alguma aresta a desse grafo,
então, a incide em v e vice-versa. Dois vértices v e w de um grafo G são adjacen-
tes (ou vizinhos) se existir uma aresta de G cujos extremos são v e w.
Observe a Figura 13 para compreender a definição anterior. A ares-
ta a4 incide sobre os vértices v1 e v3, logo, v1 e v3 são adjacentes.
Figura 13
Grafo G
Fonte: Elaborada pela autora.
v1 v3
v4
a4
a1 a2
a3
a5
v2
Portanto, a estrutura dos grafos é construída com base em modelos
matemáticos que transmitirão um resultado aproximado (ou exato) a
problemas físicos.
5.1.1 Caminhos, passeios e trilhas
Agora, vamos retomar a Figura 13 para tratar do conceito de
caminho. Ou seja, as arestas serão interpretadas como estruturas que
determinam caminhos.
Um caminho do vértice v1 para o vértice v4, no grafo G, é uma se-
quência de vértices v1, v2, v3, v4, de tal modo que (v1, v2), (v2, v3), (v3, v4)
são arestas em A. O comprimento (ou tamanho) de um caminho é o
número de arestas que ele contém.
Um caminho simples é um caminho em que todos os vértices são
diferentes, com a possível exceção do primeiro e do último. Um ciclo é
um caminho simples em que o primeiro e o último vértices são iguais.
Um ciclo também pode ser chamado de caminho fechado. Um trajeto é
um caminho no qual todas as arestas são distintas.
132 Matemática para Computação
De acordo com Nicoletti e Hruschka Júnior (2018), quando nenhuma
aresta aparece mais do que uma vez, tendo em umgrafo os vértices
u e v, sendo u o vértice inicial e v o vértice final, chamamos de trilha.
Se u ≠ v, teremos uma trilha aberta. Caso u = v, obtemos uma trilha
fechada ou circuito.
Ainda por Nicoletti e Hruschka Júnior (2018, p. 78), temos que
(1) Uma trilha é um passeio no qual nenhuma aresta é repetida.
(2) Um caminho é um passeio no qual nenhum vértice é repe-
tido. (3) Consequentemente, em um caminho nenhuma aresta
pode ser repetida, o que garante que todo caminho é uma trilha.
(4) Nem sempre toda trilha é um caminho. (5) Por definição, todo
caminho é um passeio.
Afirmamos que uma estrutura matemática é um grafo conexo (ou
interligado) se existir pelo menos um caminho entre cada par de vérti-
ces do grafo. Caso contrário, o grafo é chamado de desconexo.
Toda essa estrutura matemática pode ser usada em diversas situa-
ções aplicadas. Por exemplo, uma pequena empresa de entrega de re-
feições pode usar um modelo de grafo para resolver o problema da
entrega de refeições quentes, em um intervalo de tempo de duas horas
e com o menor custo possível para a empresa, ou seja, minimizando o
trajeto para as entregas.
Esse tipo de modelo, que não é dos mais simples, mas que pode ser
idealizado por meio dos conceitos aprendidos neste capítulo, precisa
ser resolvido em tempo real.
É nesse momento que entra a computação científica. Assim, o grafo
precisa ser escrito em um formato em que o computador possa lê-lo
e operá-lo. Para essa transcrição, serão necessários conceitos como
funções, matrizes e vetores, que viabilizarão o cálculo de problemas
logísticos como o citado anteriormente.
5.2 Representação computacional de um grafo
Vídeo Visualmente os grafos são estruturas bem fáceis de serem com-
preendidas, mas quando precisamos levar essas informações para a
área computacional, a representação gráfica pode ser um complicador.
Assim, foram desenvolvidas formas de representar os grafos por meio
de matrizes e sequências, fazendo com que a estrutura do grafo possa
ser representada computacionalmente de maneira simples.
Para conhecer um
pouco mais sobre grafos
conexos e desconexos
e visualizar exemplos
desses casos, indicamos
o material Conceito básico
da teoria de grafos.
Disponível em: https://www.inf.
ufsc.br/grafos/definicoes/definicao.
html. Acesso em: 24 ago. 2021.
Saiba mais
https://www.inf.ufsc.br/grafos/definicoes/definicao.html
https://www.inf.ufsc.br/grafos/definicoes/definicao.html
https://www.inf.ufsc.br/grafos/definicoes/definicao.html
Grafos e árvores 133
O problema das sete pontes de Königsberg tem seu grafo descrito
na Figura 14 a seguir.
A
1
2
3
4
6
7
5
B
C D
Figura 14
As setes pontes de Königsberg
Fonte: Elaborada pela autora.
Note que os vértices A, B e D têm três arestas, enquanto C tem cin-
co. O número de arestas que incide sobre cada vértice determina o
grau de um vértice. Logo, podemos afirmar que C tem grau cinco, en-
quanto A, B e D têm grau três.
O grau de um grafo é a soma dos graus de seus vértices. O teorema do
aperto de mãos (handshaking) ainda permite que escrevamos que o grau de
um grafo G é igual a duas vezes o número de arestas de G.
Euler provou que se um vértice tem um número ímpar de arestas,
então, caso queira percorrer as arestas apenas uma vez, nunca acaba-
rá no vértice que começou (GOLDBARG; GOLDBARG, 2012; NICOLETTI;
HRUSCHKA JÚNIOR, 2018).
Esse grafo pode ser representado por uma matriz chamada matriz
de adjacência, que será escrita como a seguir.
0
0
1
1
0 1 1
0 1 1
1 0 1
1 1 0
�
�
�
�
��
�
�
�
�
�
�
�
A B C D
A
B
C
D
Veremos como construir esse tipo de matriz.
O teorema de handsha-
king (aperto de mãos) é
descrito para grafos não
direcionados e finitos,
compostos por um núme-
ro par de vértices de grau
ímpar.
A analogia ao aperto de
mãos se faz, pois, supondo
que exista um grupo de
pessoas em que algumas
apertam mãos, um núme-
ro par de pessoas deve
ter apertado um número
ímpar de mãos de outras
pessoas. Isso também
nos permite afirmar que a
soma dos graus de todos
os vértices de um grafo
não direcionado finito é
duas vezes o número de
arestas desse grafo.
Em circuitos digitais o
handshaking é definido
como o processo de troca
de sinais pelo qual dois
dispositivos digitais ou
sistemas estabelecem
entre si uma comunicação
(FLOYD, 2007).
Saiba mais
134 Matemática para Computação
5.2.1 Representação por meio de
matrizes de adjacências
Dado um grafo G com n vértices, podemos representá-lo em uma
matriz que está em um espaço de tamanho |V| ⨯ |V|. Portanto, po-
demos chamá-la de B (ordem n) com |V| = n. Essa é uma matriz de
G (grafo G(V, A)), logo, denotamos Bn⨯n (G), em que os elementos de
Bn⨯n (G) serão [bij].
Os elementos bij guardam informações sobre como os vértices adja-
centes se relacionam na forma:
B i j se i j
caso contrário
( , ) , ,
,
� � �����
��
1
0
A
Se as arestas do grafo tiverem pesos, bij pode conter, no lugar de 1,
o peso (custo) dessa mesma aresta.
Na figura a seguir temos um grafo dirigido. Note que as arestas
contêm sentido duplo e essa informação foi apresentada na matriz de
adjacência.
Figura 15
Matriz de adjacência
al
ri/
Sh
ut
te
rs
to
ck
A seguir, construiremos a matriz de adjacência conhecendo o grafo
que a representa.
Para saber mais sobre
essa importante afirmação
de Euler que se tornou o
primeiro teorema da teo-
ria dos grafos, sugerimos
a obra Grafos: conceitos,
algoritmos e aplicações,
de Marco Cesar Goldbarg
e Elizabeth Goldbarg. O
teorema está descrito na
página 89 da obra.
GOLDBARG, M.; GOLDBARG, E. 1. ed.
Rio de Janeiro: Elsevier, 2012.
Já na obra Fundamentos
de teoria dos grafos para
computação, de Maria do
Carmo Nicoletti e Estevam
R. Hruschka Júnior, página
163, também é possível
acompanhar o teorema
e sua prova. Os autores
apresentam exemplos
que nos auxiliam a fixar a
ideia e visualizar diferen-
tes situações aplicadas
ao teorema.
NICOLETTI, M. C.; HRUSCHKA JÚNIOR,
E. R. 3. ed. Rio de Janeiro: LTC, 2018.
Livro
Grafos e árvores 135
Exemρlo 3
Analise o grafo a seguir (Figura 16) e escreva a matriz de adjacência dele.
Figura 16
Grafo não dirigido
a4
a1
a2
a3
a5
v1
v3
v4
v2
v5
Fonte: Elaborada pela autora.
A matriz de adjacência apresenta a conexão entre os vértices.
Assim, teremos:
0
1 0 0 1 0
0 0 0
1 0 1 0
1 1
1 1 1 0 0
0 0 1 0 0
�
�
�
�
�
��
�
�
�
�
�
�
�
�
v1 v2 v3 v4 v5
v1
v2
v3
v4
v5
B =
Quando trabalhamos com grafos direcionados, podemos adotar a
chamada matriz de incidência. Assim, usa-se o sinal positivo ou negativo
em relação aos vértices e às suas arestas incidentes, deixando evidente
o vértice de chegada ou de partida.
Com isso, se desejamos representar matricialmente um grafo G com
n vértices e m arestas, podemos escrever uma matriz Bn⨯m da forma:
B i j
se a aresta j sai do vértice i
se( , )
,
,�
�1
1
a arresta j chega no vértice i
0, caso contrário
�
�
�
��
Para compreender mais
sobre a matriz de adjacên-
cia, sugerimos assistir ao
vídeo Algoritmos e Estrutu-
ras de Dados - USP - Matriz
de Adjacência em Grafos.
Disponível em: https://youtu.be/
q3lh8NcmH14. Acesso em: 24
ago. 2021.
Vídeo
https://youtu.be/q3lh8NcmH14
https://youtu.be/q3lh8NcmH14
136 Matemática para Computação
Esse conceito pode ser observado por meio do digrafo apresentado
na Figura 17. Note que a matriz de incidência foi montada respeitando
as relações entre arestas direcionadas e nós.
B i j
a a a
( , ) �
�
�
�
�
�
�
�
�
�
�
�
�
�
1
2
3
1 0 1
1 1 0
0 1 1
1 2 3
Figura 17
Digrafo com três vértices e três arestas
a1
a2
a3
1
2
3
Fonte: Elaborada pela autora.
Além da representação matricial, podemos representar os grafos
por intermédio de listas. Na computação, chamamos de listas as estru-
turas de dados que permitem armazenar informações de determinadotipo em uma ordem previamente especificada. Uma lista pode armaze-
nar, por exemplo, informações dos vértices ou das arestas.
A implementação das listas pode ser feita por meio de arrays ou
encadeamentos. Uma matriz é um array multidimensional. Já um vetor
é um array unidimensional.
Cada elemento de um array deve ser colocado em uma posição es-
pecífica e, caso seja necessário retirar algum elemento dele, pode ha-
ver a necessidade de reposicionamento dos elementos restantes.
Já o encadeamento envolve conceitos de programação, como pon-
teiros e referências.
Para criar listas encadeadas, é preciso que os elementos da lista
referenciem algum outro elemento, ou seja, indiquem onde podemos
encontrar um outro elemento. As listas de adjacência, as quais vere-
mos na sequência, são listas encadeadas, pois têm os vértices fazendo
referência a outros vértices conectados a eles.
Vamos entender esse conceito como mais uma proposta de repre-
sentação computacional dos grafos.
Grafos e árvores 137
5.2.2 Representação por meio de lista de adjacências
Uma lista de adjacência em um grafo será composta por todos os
vértices nos quais existe uma aresta como conexão. Nesse caso, essa
será a lista de adjacência desse vértice.
Considere o grafo representado na Figura 18 a seguir.
Figura 18
Grafo não dirigido de cinco nós e cinco arestas
Fonte: Elaborada pela autora.
a4
a1
a2
a3
a5
v1
v3
v4
v2
v5
Teremos as seguintes listas vinculadas aos vértices v1, v2, v3, v4 e v5,
respectivamente:
• Adj[v1] = [v2,v4];
• Adj[v2] = [v1,v4];
• Adj[v3] = [v4,v5];
• Adj[v4] = [v1,v2,v3];
• Adj[v5] = [v3].
Em um grafo dirigido, o princípio será o mesmo. Assim, seja o
grafo a seguir (Figura 19), montaremos as listas de adjacência refe-
rentes a cada vértice.
138 Matemática para Computação
Figura 19
Digrafo de 3 vértices
Fonte: Elaborada pela autora.
a1
a2
a3
v2
v1
v3
Esse grafo será representado pelas seguintes listas de adjacência:
• Adj[v1] = [ ];
• Adj[v2] = [v1];
• Adj[v3] = [v1, v2].
Note que as listas de adjacência de cada vértice respeitam o sen-
tido da aresta.
Portanto, é possível escolher por representações computacionais
distintas. Essa escolha levará em consideração: características especí-
ficas da aplicação, seleção da linguagem de programação, necessidade
de representação visual, dentre outras características.
5.3 Conceito de árvore
Vídeo Talvez o exemplo mais simples que nos permita entender o conceito
de árvore seja a árvore genealógica (Figura 20).
Iv
an
A
le
x
Bu
rc
ha
k/
Sh
ut
te
rs
to
ck
Figura 20
Árvore genealógica
Grafos e árvores 139
Isso mesmo, a árvore genealógica que estudamos desde a educação
infantil, a qual construímos diversas vezes em sala de aula e permite
entendermos nossa ancestralidade, é um grafo com características dis-
tintas que possibilita que a nomeemos de árvore.
Matematicamente, uma árvore é um grafo conexo sem ciclos.
Com o desenvolvimento da teoria dos grafos, muitas áreas benefi-
ciaram-se de suas definições, para que pudessem ser estruturadas e
melhor explicadas conceitualmente.
Gustav Robert Kirchhoff, nascido em Königsberg (1824-1877), exa-
tamente onde toda a teoria dos grafos começou, utilizou-a para de-
senvolver e validar seu trabalho com circuitos elétricos, tendo como
particular conceito nessa construção as árvores.
Esses resultados serviram de incentivo para que outros pesquisa-
dores e cientistas, das mais diversas áreas, utilizassem esses conceitos
em seus trabalhos.
Como vimos, uma lista encadeada é uma estrutura de dados linear.
Nela, os elementos do conjunto são associados por relações de “poste-
rior” ou “anterior”, na intenção de criar uma espécie de fileira imaginária.
As árvores são estruturas de dados não lineares, nas quais os ele-
mentos costumam ser associados por relações de “esquerdo”, “direito”,
“inferior”, “superior”, “pai”, “filho”, “menor”, “maior” etc. Essas estrutu-
ras formam grafos conexos e acíclicos. Quando representados gra-
Aa
ar
gl
~c
om
m
on
sw
ik
i/W
ik
im
ed
ia
C
om
m
on
s
Gustav Robert Kirchhoff
Figura 21
Tipos de árvores de
decisão
Ze
rn
L
ie
w/
Sh
ut
te
rs
to
ck
O material de aula do
professor José Augusto
Baranauskas, do depar-
tamento de ciência da
computação e matemática
da Universidade de São
Paulo, apresenta conceitos,
exercícios e aplicações
computacionais sobre gra-
fos e árvores. Os exemplos
são bastante didáticos e
os exercícios auxiliam na
melhor compreensão do
tema estudado.
Disponível em: http://dcm.ffclrp.
usp.br/~augusto/teaching/aedii/
AED-II-Grafos.pdf. Acesso em: 24
ago. 2021.
Saiba mais
ficamente, formam diagramas
que remetem à estrutura física
de uma árvore (da natureza), com
galhos ramificados.
De acordo com Almeida (2018,
p. 19), “como nem todo grafo é
uma árvore, podemos afirmar
que um grafo será uma árvore se
e somente se existir um único ca-
minho entre dois vértices quais-
quer deste grafo”. Todo grafo
conexo tem, ao menos, uma árvo-
re composta de todos seus vérti-
ces e algumas de suas arestas.
http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf
http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf
http://dcm.ffclrp.usp.br/~augusto/teaching/aedii/AED-II-Grafos.pdf
140 Matemática para Computação
Vamos entender esse princípio: considere o grafo apresentado
na Figura 22.
Figura 22
Conceito de árvore geradora
Fonte: Elaborada pela autora.
a1
a4
a5
a6 a2
a3
v2
v5v6 v4
v1 v3
Observe que se retirarmos a aresta a3, ainda assim todos os vértices
estarão interligados. Com isso, se os vértices são, por exemplo, pontos
de entregas de produtos e queremos analisar qual o caminho mínimo
para passarmos por todos esses pontos, precisaremos que eles este-
jam conectados, mas não necessariamente usaremos todas as arestas
como vias de acesso aos pontos de entrega.
Nesse momento entramos em um conceito chamado caminho míni-
mo, que explicaremos melhor na sequência.
Mas, independentemente de sabermos qual seria o trajeto mais
curto, precisamos encontrar todas as árvores possíveis presentes
nesse grafo, ou seja, todas as formas de chegarmos a todos os vértices
sem que exista dualidade entre os caminhos. Esse tipo de problema é
conhecido como problema de roteamento.
As três figuras a seguir apresentam as árvores geradoras para o gra-
fo apresentado na Figura 22, observe.
Figura 23
Primeiro exemplo de árvore geradora
Fonte: Elaborada pela autora.
a1
a4
a5
a6 a2
v2
v5v6 v4
v1 v3
Grafos e árvores 141
Figura 24
Segundo exemplo de árvore geradora
Fonte: Elaborada pela autora.
a4
a5
a6 a2
a3
v2
v6 v4
v1
v5
v3
Figura 25
Terceiro exemplo de árvore geradora
Fonte: Elaborada pela autora.
a5
a1
a6 a2
a3
v2
v6 v4
v1
v5
v3
Em qualquer uma das três árvores temos todos os pontos de entrega
interconectados. Com isso, podemos começar a pensar em qual dessas
três árvores geradoras temos um conjunto de rotas que minimiza a dis-
tância para as entregas, ou seja, qual é a árvore geradora mínima.
Note que, nesse caso, é necessário conhecermos o valor das arestas
ou a função aplicada em cada um desses caminhos, que pode levar em
consideração a distância, o custo do combustível, o tipo de meio de
locomoção usado etc. Portanto, para esse fim, precisamos de um grafo
com pesos. Observe a definição a seguir.
Definição 3
Uma árvore geradora mínima, para um grafo com pesos, é uma árvore geradora
que tem o menor peso total possível dentre todas as possíveis árvores gerado-
ras do grafo.
142 Matemática para Computação
Note que dependendo da quantidade de vértices e arestas de um
grafo, o número de árvores geradoras pode ser enorme. Por exemplo,
o grafo de Petersen, que pode ser analisado na Figura 26 a seguir, tem
2.000 árvores geradoras.
Figura 26
Grafo de Petersen
Le
sh
ab
iru
ko
v/
W
ik
im
ed
ia
C
om
m
on
s
Existem alguns algoritmos conhecidos para se obter uma árvore
geradora mínima. Desses, o algoritmo de Kruskal(1956) e algoritmo
de Prim (1957) talvez sejam os mais populares. Ambos são chamados
de algoritmos gulosos, pois fazem escolhas levando em consideração a
melhor solução imediata (mais próxima).
Com os algoritmos de busca aplicados aos grafos e, particularmen-
te, às árvores, notamos um campo imenso de aplicações possíveis que
vai muito além dos denominados problemas de roteamento.
Na sequência, vamos ver mais alguns conceitos importantes sobre
árvores que podem ser aplicados a procedimentos de busca.
5.4 Raízes e árvores binárias
Vídeo Como foi mencionado nas seções anteriores, uma árvore é um gra-
fo conexo e acíclico. Na formação de uma árvore, podemos destacar al-
guns pontos importantes, sendo um deles o conceito de raiz da árvore.
Uma árvore que apresenta um vértice distinto facilmente distinguí-
vel é chamada árvore enraizada (Figura 27). Esse vértice é considerado
o vértice raiz. Nesse caso, afirmamos que os vértices têm hierarquia.
Assista aos vídeos Algo-
ritmo de Kruskal - Árvore
Geradora Mínima e Algo-
ritmo de Prim – Teoria dos
Grafos (Exemplo Prático).
Disponível em: https://www.youtube.
com/watch?v=3Q6RdxGmDgQ.
Acesso em: 24 ago. 2021.
Disponível em: https://www.
youtube.com/watch?v=Pgf-
AL1vYb4. Acesso em: 24 ago. 2021.
Vídeo
Os algoritmos de Kruskal
e de Prim podem ser
encontrados em diversas
obras específicas sobre
grafos. Sugerimos a obra
Grafos: introdução e práti-
ca, de Boaventura Netto e
Jurkiewicz, p. 86 (Kruskal)
e p. 87 (Prim).
BOAVENTURA NETTO, P. O;
JURKIEWICZ, S. 2. ed. São Paulo:
Blücher, 2017.
Saiba mais
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
https://www.youtube.com/watch?v=3Q6RdxGmDgQ. Acesso em: 24 ago. 2021.
Disponível em: https://www.youtube.com/watch?v=Pgf-AL1vYb4
Grafos e árvores 143
Podemos montar uma árvore genealógica como uma árvore enrai-
zada. Para isso, escolhemos um dos membros para o primeiro casal e
partimos dali para seus filhos e assim sucessivamente.
Figura 27
Árvore enraizada
to
vo
va
n/
Sh
ut
te
rs
to
ck
É visível a identificação da raiz de uma árvore, e sua localização é mui-
tas vezes considerada o ponto de partida para algoritmos de busca para
esse tipo de árvore. Uma árvore não enraizada é uma árvore dita livre.
Nicoletti e Hruschka Júnior (2018, p. 184) trazem a seguinte definição
para árvore binária: “é um grafo vazio ou tem um vértice especial r chama-
do raiz, e os demais vértices da árvore são subdivididos em dois subcon-
juntos disjuntos: as subárvores esquerda e direita de r, as quais são
também árvores binárias”. A Figura 28 exemplifica tipos dessas árvores.
Figura 28
Tipos de árvores binárias
Sh
ad
eD
es
ig
n/
Sh
ut
te
rs
to
ck
Árvore equilibrada ou
árvore binária cheia
Árvore em
profundidade
Árvore em largura
144 Matemática para Computação
Uma árvore binária pode ser dita completa ou incompleta. A seguir
temos a definição de árvore binária completa.
Definição 4
Uma árvore binária completa é uma árvore enraizada, tal que existe exatamente
um vértice de grau dois e cada um dos vértices restantes tem grau um ou três.
Naturalmente, o vértice de grau dois é o vértice raiz da árvore.
Caso a definição não se verifique, temos uma árvore binária incompleta.
Uma aplicação envolvendo árvores binárias pode ser encontrada
em trabalhos sobre otimização e distribuição de sinal em redes. Tam-
bém existem aplicações na área de redes óticas e otimização de siste-
mas submersos para gerenciamento de extração de petróleo 1 .
Algumas propriedades das árvores binárias permitem que possa-
mos estimar o número de operações, vértices e arestas envolvidas na
solução de um algoritmo de busca. Vamos conhecê-las a seguir.
5.4.1 Propriedades de árvores binárias
As árvores binárias costumam ser usadas em diversas aplicações
por sua característica essencial, a qual é a de permitir que seja tomada a
decisão entre dois caminhos (direita ou esquerda) até que se chegue
a um objetivo determinado.
Assim, para chegarmos ao objetivo com rapidez e eficiência, é essencial
entendermos algumas propriedades e operações que permitem calcular
o número de vértices e arestas e compreendermos operações usadas em
um algoritmo de busca que tem como base uma árvore binária.
O número de vértices em uma árvore binária completa (com
três ou mais vértices) é sempre ímpar. Já uma árvore binária comple-
ta com n vértices terá p n� �1
2
vértices pendentes, que são o objetivo
da busca.
A altura h de uma árvore binária é a distância entre a raiz e seu
descendente 2 mais afastado.
Se T é uma árvore binária completa composta por p vértices pen-
dentes e tem altura h, então:
Alguns desses exemplos
podem ser observados
no livro de Nicoletti e
Hruschka Júnior (2018).
1
Um descendente em
uma árvore binária é
qualquer vértice (nó) que
possa ser atingido por
meio da decisão entre os
dois caminhos possíveis
(direita ou esquerda) em
qualquer ordem.
2
Grafos e árvores 145
I. p ≤ 2h
II. h p l n� � � �|log | | og |2 2
1
2
1
Conhecendo a estrutura dos grafos, suas designações e proprieda-
des, trazemos, a seguir, a interpretação do conceito de procedimentos
de busca.
5.5 Introdução a procedimentos de busca
Vídeo Árvore binárias e árvores geradoras mínimas são muito utilizadas
em procedimentos de busca. Isso ocorre, pois esse tipo de grafo é co-
mumente aplicado em testes que apresentam duas possíveis respostas.
Tendo como ponto de partida a raiz da árvore, o teste é iniciado e
nos encaminha para um dos dois vértices da próxima camada (nível)
em que novos testes são efetuados.
Quando atingimos o objetivo da busca (vértice pendente), o proce-
dimento de busca se encerra. Com isso, entender os procedimentos de
busca depende da definição do conceito de distância entre vértices (nós).
Tendo em um grafo os vértices u e v, sendo u o vértice inicial e
v o vértice final, calcular a distância ou o comprimento do caminho entre
esses dois vértices depende de algumas propriedades algébricas, como:
I. d(u, v) ≥ 0 e d(u, v) = 0 se, e somente se, u = v.
II. d(u, v) = d(v, u) – comutatividade.
III. d(u, v) + d(v, w) ≥ d(u, w) – desigualdade triangular.
O grafo da Figura 29 representa graficamente a distância medindo
uma unidade de medida em cada aresta.
Figura 29
Distância 1 em cada aresta
Fonte: Elaborada pela autora.
1
1
1
1
v1
v2
v4
v3
146 Matemática para Computação
A matriz de distâncias tem como elementos a distância entre os vér-
tices que a compõem. Observe a seguir a matriz de distância Dist(G)
referente ao grafo da Figura 29.
Dist G( ) �
1 2 1
0
1 0 1 2
2 1 0
1
1 2 1 2
�
�
�
�
�
�
�
�
�
�
�
�
v1 v2 v3 v4
v1
v2
v3
v4
Note que a matriz de distância é construída para a menor distância
entre dois vértices.
Nos procedimentos de busca mais conhecidos estão os chamados:
procedimentos de busca em profundidade (depth first) e os procedimentos
de busca em largura (breadth first)
A busca em profundidade é um algoritmo que caminha pelo grafo bus-
cando, sempre que possível, o descendente mais distante (o mais profundo).
A estratégia desse tipo de busca é, com base em um vértice v
recém-descoberto, explorar as arestas que partem de v que ainda não
foram exploradas.
Quando todas as arestas adjacentes a v forem visitadas, a busca come-
ça a explorar os vértices para trás, tais que estes saiamdo vértice v já
descoberto.
O algoritmo é a base para muitos outros algoritmos importantes,
tais como: a verificação de grafos acíclicos, a ordenação topológica e os
componentes fortemente conectados.
Já a busca em largura visa encontrar o comprimento de um cami-
nho entre um vértice e seu descendente mais distante, usando o me-
nor número de arestas.
De acordo com Goldbarg e Goldbarg (2012, p. 65), a busca em largura
pode ser definida como: “uma busca é denominada em largura se, para o
critério de seleção de vértices, for exigido que a escolha seja feita sobre o
vértice não marcado menos recentemente alcançado na busca”.
Com essas duas estratégias de busca determinadas, podemos
apresentar alguns dos algoritmos mais conhecidos que as utilizam
e que permitem calcular o caminho mínimo para a obtenção de um
vértice pendente.
Conheceremos alguns desses algoritmos a seguir.
Para conhecer um pouco
mais sobre os algoritmos
de busca, sugerimos a
leitura do material Algorit-
mos em grafos, elaborado
por Charles Ornelas
Almeida, Israel Guerra e
Nivio Ziviani.
Disponível em: http://www2.dcc.
ufmg.br/livros/algoritmos/cap7/
slides/pascal/completo1/cap7.pdf.
Acesso em: 24 ago. 2021.
Leitura
http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf
http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf
http://www2.dcc.ufmg.br/livros/algoritmos/cap7/slides/pascal/completo1/cap7.pdf
Grafos e árvores 147
5.5.1 Algoritmos de caminho mínimo
A teoria dos grafos é largamente utilizada em problemas de rotea-
mento, sendo, nesses casos, usados os chamados algoritmos de busca.
Dentre os algoritmos mais conhecidos, encontram-se o algoritmo do
vizinho mais próximo, o algoritmo de Dijkstra, o algoritmo de Floyd etc.
O algoritmo de Dijkstra tem como conceito base a construção de
uma matriz de distâncias, a qual terá seus elementos sendo a menor
distância entre dois vértices.
O cientista da computação holandês, Edsger Wybe Dijkstra, nasceu
em Roterdã, 1930, e faleceu em Nuenen. Ele fez diversas contribuições
nas áreas de desenvolvimento de algoritmos, sistemas operacionais e
processamento distribuído. Em 1972, recebeu o prêmio Turing por suas
contribuições no desenvolvimento de linguagens de programação.
O conjunto S que será construído com base no algoritmo Dijkstra é
composto por vértices cujos caminhos mais curtos até um vértice origem
já são conhecidos. Esse conjunto produz uma árvore de caminhos mais
curtos de um vértice origem s para todos os vértices que são alcançáveis
a partir de s.
Não vamos nos aprofundar na estrutura desses algoritmos, pois,
como comentamos no início do capítulo, a teoria dos grafos é bastante
extensa, riquíssima e existem obras específicas sobre o tema. Mas caso
tenha curiosidade para conhecer e até implementar esses algoritmos,
sugerimos alguns materiais.
O Problema do Caixeiro-viajante (PCV) é do tipo “caminho mínimo”. Seu algoritmo
é estruturado para que seja possível visitar, em ordem sequencial, um conjunto
de pontos dispersos de um grafo, ou seja, sair de um vértice inicial, visitar todos os
outros e voltar para a origem inicial sem repetir nenhum vértice.
Podemos indicar muitas aplicações que usam o PCV. Dentre elas, escolhemos o
artigo publicado pela Associação Brasileira de Engenharia de Produção (ABREPO),
intitulado Teoria dos grafos aplicada à roteirização na logística de distribuição: o
problema do caixeiro viajante em uma empresa fabricante de farinha de trigo.
Acesso em: 24 ago. 2021.
http://www.abepro.org.br/biblioteca/TN_STO_291_1644_39148.pdf
Artigo
Assim, vimos a estrutura de um grafo e suas ramificações. Conhe-
cemos as terminologias do tema, alguns tipos de grafos e formas de
representação computacional, que nos deram uma base importante e
que conecta a matemática e a computação de maneira aplicada.
Assista aos dois vídeos
sobre os algoritmos de
Floyd e Dijkstra, Algoritmo
de Floyd e Algoritmo de
Dijkstra. Escolha uma
linguagem de progra-
mação de seu domínio e
reflita sobre as possibili-
dades de implementação
computacional de um ou
mais algoritmos de busca
nessa linguagem.
Disponível em: https://youtu.be/Dfga-
Bkp02HY. Acesso em: 24 ago. 2021.
Disponível em: https://youtu.be/vzW-
VCqYDlAs. Acesso em: 24 ago. 2021.
Vídeo
Ha
m
ilt
on
R
ic
ha
rd
s/
W
ik
im
ed
ia
C
om
m
on
s
Edsger Wybe Dijkstra
https://pt.wikipedia.org/wiki/Roterd%C3%A3
https://pt.wikipedia.org/wiki/1930
https://pt.wikipedia.org/wiki/Nuenen
https://youtu.be/DfgaBkp02HY
https://youtu.be/DfgaBkp02HY
https://youtu.be/vzWVCqYDlAs
https://youtu.be/vzWVCqYDlAs
148 Matemática para Computação
CONSIDERAÇÕES FINAIS
Fechamos o capítulo destinado à teoria dos grafos e árvores e espera-
mos que, após esta introdução, você esteja curioso para aprender ainda
mais sobre esse tema tão rico e aplicável em nosso cotidiano e em outras
áreas do conhecimento.
Podemos até afirmar que as relações sociais por meios digitais não
existiriam sem a teoria dos grafos e que nossa comida chegaria gelada
caso o entregador de pizza não otimizasse sua rota de entrega.
Percebemos que muito dessa teoria é aplicada mesmo sem notarmos
sua existência ou importância. Mas agora que você conhece um pouco so-
bre ela, poderá enxergar a matemática por trás de tarefas simples e com-
plexas, por exemplo, as conexões neurais realizadas pelo nosso cérebro.
Sim, elas também podem ser representadas por grafos.
Indicamos que acesse os materiais sugeridos como complementação
do conteúdo. Acreditamos que o tripé teoria, prática e aplicação é ne-
cessário para a boa compreensão de qualquer conceito.
ATIVIDADES
Construa uma matriz de adjacência e uma matriz de incidência para o
grafo apresentado a seguir e descreva as diferenças entre os dois resul-
tados. Note que a1 = [v4, v1], a2 = [v5, v2], a3 = [v1, v3], a4 = [v2, v4]
e a5 = [v3, v5].
v1
v5
a1
a2
a3
a5 a4
v2
v4 v3
Atividade 1
Grafos e árvores 149
Seja o grafo exposto na figura a seguir.
v1
v6
v5 v2
v4 v3
Apresente uma árvore geradora para esse grafo usando o conceito de
extração de arestas.
Atividade 2
Usando as árvores binárias, desenvolva um grafo para representar
a quantidade de jogos necessários em um torneio de vôlei com 16
inscritos.
Atividade 3
REFERÊNCIAS
ALMEIDA, L. de A. e. Árvores: algoritmos e aplicações. 2018. Dissertação (Mestrado em
Matemática) – Instituto de Matemática Pura e Aplicada, Rio de Janeiro. Disponível em:
https://impa.br/wp-content/uploads/2018/03/TCC_2018_Lauro-e-Almeida.pdf. Acesso em:
23 ago. 2021.
BOAVENTURA NETTO, P. O; JURKIEWICZ, S. Grafos: Introdução e prática. São Paulo:
Blücher, 2017.
FLOYD, T. L. Sistemas digitais: fundamentos e aplicações. Porto Alegre: Bookman, 2007.
GOLDBARG, M.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. Rio de Janeiro:
Elsevier, 2012.
GOOGLE EARTH. 2021. Disponível em: https://earth.google.com/web/search/Kalinin-
grad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.1195937
9a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyM-
WE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pb-
mdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q-
3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA. Acesso em: 23 ago. 2021.
NICOLETTI, M. C.; HRUSCHKA JÚNIOR, E. R. Fundamentos da teoria dos grafos para
computação. Rio de Janeiro: LTC, 2018.
https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA
https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwAhttps://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA
https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA
https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA
https://earth.google.com/web/search/Kaliningrad,+Oblast+de+Kaliningrado,+R%c3%bassia/@54.6947304,20.56456713,4.11959379a,6991.5150592d,35y,0h,0t,0r/data=CpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyMWE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCG_x6pSxHM0QCosS2FsaW5pbmdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q3wBHfS-j8FUg3wBnqs6-zuJxHwCGsWQUE7aBHwA
150 Matemática para Computação
Resolução das atividades
1 Por que estudar matemática?
1. Sabendo que um algoritmo é compreendido como um processo
que mostra detalhadamente os métodos necessários para
a resolução de uma atividade, e que podemos pensar nessa
estrutura em formato de pseudocódigo como estrutura
inicial, descreva um pseudocódigo para o cálculo da expressão
numérica 1 + 3(5 + 1).
Início:
Sejam os números 1, 3 e 5 dispostos como 1 + 3(5 + 1), então:
Resolva a operação dentro dos parênteses.
Se encontrar multiplicação ou divisão, resolva.
Caso contrário, resolva a adição ou a subtração.
Após eliminar os parênteses, resolva.
Se encontrar multiplicação ou divisão, resolva.
Caso contrário, resolva a adição ou a subtração.
Finalize imprimindo o resultado da expressão.
Fim.
2. Descreva o modelo matemático que pode ser utilizado para
representar a definição do problema a , para a > 0, usando
apenas as quatro operações aritméticas.
Conseguimos transformar o problema real dado por a , com a > 0
usando a expressão
x a=
x2 = a
Logo,
f(x) = x2 – a
Assim, determinando a raiz de f(x), que se transformará em uma
equação do segundo grau da forma
x2 – a = 0
percebemos que essas raízes serão a e − a� .
Resolução das atividades 151
3. Uma pesquisa foi realizada coletando dados referentes à altura
de alunos de uma sala de aula. Esse tipo de dado é qualitativo
ou quantitativo? Justifique.
A altura coletada de um grupo de pessoas é um dado quantitativo. Esse
tipo de dado pode ser classificado por meio de relações numéricas de
intervalos de classe por se tratar de um dado numérico que não
pode ser representado por um número inteiro, havendo a necessidade
de ser representado por um decimal, que pode assumir qualquer
valor após a vírgula, por exemplo, 152,1 cm. É também chamado de
dado quantitativo contínuo.
2 Noções sobre sistemas de numeração
1. Podemos considerar o sistema de numeração romano um
sistema aditivo ou um sistema posicional? Explique.
O sistema de numeração romano, usado em algumas representações
até hoje, como em relógios e para marcar itens, é um sistema aditivo,
e podemos perceber essa dinâmica, por exemplo, quando precisamos
escrever números como 20 (XX) e 30 (XXX), conforme é apresentado
na figura a seguir.
im
ag
es
to
ck
de
si
gn
/S
hu
tte
rs
to
ck
Números Romanos
Ele é um típico sistema de numeração aditivo, mas que teve alguns
avanços quando comparado a sistemas desse tipo que não permitiam
a escrita rápida de números muito grandes.
2. É possível converter um número na base 10 para a base
hexadecimal por meio de divisões sucessivas? Explique essa
conversão e converta o número (9)10 para essa base.
152 Matemática para Computação
Como a base hexadecimal é composta de um número de algarismos
maior do que a base 10, qualquer número menor que 10 não precisa
ser convertido, sendo escrito diretamente na sua forma decimal e
apenas corrigindo a base.
Assim, para o número (9)10 teremos (9)10 = (9)16.
Contudo, se esse número fosse maior do que 9, por exemplo, se
tivéssemos (10)10, teríamos como conversão (10)10 = (A)16.
Por meio da divisão, precisamos fazer 10 ÷ 16 = 0 → Resto 10. Nesse
caso, precisamos compreender quem é o representante para 10 na
base hexadecimal, e esse elemento é a letra A, portanto (A)16 = (10)10.
3. Considere a escrita do número de Napier da forma e = 2,718... e
e
n
n
� � � � � ��
�
�
0
1 1
0
1
1
1
2
1
3
�
! ! ! ! !
No primeiro caso, devemos usar qual tipo de ajuste numérico
para obter um número finito? E no segundo caso? Quais são os
erros envolvidos em cada um dos casos?
Ao escrever o número de Napier da forma e = 2,718 ..., precisamos
fazer um arredondamento para obter um número finito. Nesse caso,
teríamos o valor e ≈ 2,72, que acarretará um erro de arredondamento.
Quanto ao segundo caso:
e
n
n
� � � � � ��
�
�
0
1 1
0
1
1
1
2
1
3
�
! ! ! ! !
Como temos uma série numérica, podemos transformar e para
uma forma finita por meio de um truncamento nos termos da série.
Portanto, teremos um típico erro de truncamento.
3 Matrizes
1. Nas regras do xadrez, cada peça tem uma movimentação
possível. Por exemplo, o cavalo só pode se movimentar em “L”,
ou seja,
• duas casas para a direita (ou para a esquerda) e uma para
frente (ou para trás);
• uma casa para a direita (ou para a esquerda) e duas casas
para frente (ou para trás).
Resolução das atividades 153
A figura a seguir é um exemplo das possíveis movimentações
que um cavalo na casa 4D pode fazer.
8
7
6
5
4
3
2
1
HGFEDCBA
Explique, usando a notação “linha-coluna”, as possíveis
movimentações do cavalo branco que está na casa 1G
(observação: ele não pode ficar sobre outra peça branca).
Sabendo das possíveis movimentações do cavalo e assumindo que
o cavalo branco, que precisa ser movimentado, está na posição 1G,
conforme a figura, temos que este poderia se mover para as casas
3F ou 3H.
Va
pa
rt/
Sh
ut
te
rs
to
ck
154 Matemática para Computação
2. De acordo com o conceito de base para um espaço de vetores,
indique dois conjuntos de vetores que formam uma base para o
ℝ³. Justifique o porquê dessas escolhas.
Podemos escolher muitos conjuntos com a característica de serem
base para ℝ³. Todos eles precisam respeitar dois conceitos:
• serem formados por vetores LI;
• gerarem ℝ³.
Assim, respeitando esses parâmetros, definimos:
• o conjunto de vetores canônicos V = {e1, e2, e3}, em que e1 = (1, 0, 0),
e2 = (0, 1, 0) e e3 = (0, 0, 1);
• W = {v1, v2, v3}, em que v1 = (1, 2, 3), v2 = (–1, 3, 5) e v3 = (0, 1, 4).
Tanto V como W são formados por vetores linearmente independentes.
Para verificar essa condição, basta calcular o determinante de ordem 3,
composto pelos vetores de cada um desses conjuntos:
V �W� � � � � � �
1 0 0
0 1 0
0 0 1
1 0
1 2 3
1 3 5
0 1 4
12 0;
Além disso, tanto W como V são conjuntos formados por vetores
tridimensionais, sendo, assim, necessários e suficientes para gerarem
todo o ℝ³.
3. Explique por que afirmamos que a decomposição LU não é
única.
Quando realizamos a decomposição LU, obtemos duas matrizes
na forma:
A
a a
a a
l
l l
um
m mm m mm
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11 1
1
11
1
110�
� � �
�
�
� � �
�
��
� � �
�
u
u
L U
m
mm
1
0
�
�
�
�
�
�
�
�
�
�
� �
Em geral, a matriz L carrega, na sua diagonal principal, elementos
iguais a 1. Contudo, a matriz U, que tem, em sua diagonal principal,
elementos que ainda podem ser fatorados, poderia ser escrita com
outros tipos de fatoração, pensandona fatoração dos elementos da
diagonal principal e carregando esse ajuste para a matriz L. Desse
modo, existem diversas maneiras de escrever LU, para obtermos A
como resultado.
Resolução das atividades 155
4 Sistemas de equações lineares
1. Seja A a matriz dos coeficientes de um sistema de equações
lineares do tipo Ax = b, por que precisamos ter det ≠ 0 para
garantir a inversão dessa matriz? Explique.
De maneira aplicada, resolver um sistema de equações lineares é
procurar a intersecção entre as estruturas que o formam. Portanto,
precisamos garantir que os vetores que fazem parte desse
sistema sejam linearmente independentes. Caso esses vetores
sejam linearmente dependentes, precisamos do vetor de termos
independentes para garantir algum tipo de solução.
Matematicamente a inversa de uma matriz A, quadrada, pode ser
calculada pela expressão
A
det A
adj A� � � � � �� �
1 1
Portanto, se det = 0, recairemos em uma divisão que não pode ser
realizada, o que inviabiliza o cálculo da inversa de A.
2. Um sistema de equações lineares pode ter como solução infinitas
soluções. Isso é válido para o sistema a seguir? Justifique.
x y z
x y z
x y z
� � �
� � �
� � � � �
�
�
�
�
�
1
2 2 2 2
1
Nesse sistema, rapidamente percebemos que todas as equações que
o compõem são equações de planos. Ainda, os coeficientes dessas
equações são proporcionais. Assim, se montarmos a matriz ampliada
e a escalonarmos, obteremos
1 1 1 1
2 2 2 2
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
~
|
|
|
Isso significa que pa = pc = 1 e n = 2 > pa, portanto temos um sistema
compatível e indeterminado, permitindo-nos concluir que temos
infinitas soluções. Nesse caso, teremos geometricamente três planos
coincidentes, os quais podem ser observados em: https://www.
geogebra.org/3d/uypbwxrt.
https://www.geogebra.org/3d/uypbwxrt
https://www.geogebra.org/3d/uypbwxrt
156 Matemática para Computação
3. Explique, com suas palavras, o que significa a análise de
convergência de um método e qual é a sua importância para
garantir o resultado encontrado.
Basicamente a análise de convergência é o que nos permite decidir
se o método leva a uma solução que se aproxima da solução exata ou
não. Os métodos ditos numéricos em geral são descritos por processos
iterativos, que, por sua vez, só são válidos se a solução aproximada
convergir para a solução exata.
Quando analisamos a ordem de convergência e taxa de convergência,
já estamos considerando que o método converge (primeira análise a
ser verificada). A ordem de convergência e taxa de convergência nos
mostrarão como essa solução aproximada converge para a solução
real e em qual velocidade.
5 Grafos e árvores
1. Construa uma matriz de adjacência e uma matriz de incidência
para o grafo apresentado a seguir e descreva as diferenças entre
os dois resultados. Note que a1 = [v4, v1], a2 = [v5, v2], a3 = [v1, v3],
a4 = [v2, v4] e a5 = [v3, v5].
v1
v5
a1
a2
a3
a5 a4
v2
v4 v3
Resolução das atividades 157
Como o grafo é direcionado, a adjacência leva em consideração o
sentido da aresta. Usando B(i,j)= 1, se i, j A
0, caso contrário
�� ��
�
�
��
, teremos a matriz de
adjacência da seguinte forma:
matriz de adj =
0 1 0 0
0 0
0
0 11 0
0 0 0 1
1 0 0 0
0 1
0
0
0 0 0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
v1 v2 v3 v4 v5
v1
v2
v3
v4
v5
Para a matriz de incidência usamos:
B(i,j)=
-1, se a aresta j sai do vértice i
1, se a areesta j chega no vértice i
0, caso contrário
�
�
�
��
Portanto,
matriz�de�inc
v
v
v
v
v
�
�
�
�
�
�
�
�
�
�
1
2
3
4
5
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
0 1 0 0 1
��
�
�
�
�
�
�
�
�
�
�
�
a a a a a1 2 3 4 5
Note que a matriz de incidência, ao contrário da matriz de adjacência,
tem em sua diagonal principal todos os elementos iguais a 1. Isso ocorre
porque temos a incidência da aresta 1 sobre o vértice 1 e assim por
diante, até o vértice e a aresta 5. Já no caso da matriz de adjacência, a
análise é sobre a adjacência entre os vértices. Desse modo, a diagonal
principal é formada apenas por elementos nulos, pois um vértice i não
exerce influência sobre outro vértice i.
Logo, a principal diferença está na questão de que a matriz de
adjacência, assim como a lista de adjacência, analisa a adjacência entre
vértices. Já a incidência é uma relação entre aresta e vértice.
158 Matemática para Computação
2. Seja o grafo exposto na figura a seguir.
v1
v6
v5 v2
v4 v3
Apresente uma árvore geradora para esse grafo usando o
conceito de extração de arestas.
Podemos descrever algumas árvores geradoras, mas escolhemos a
seguinte:
v5
v1
v6
v2
v3v4
Note que todos os vértices são acessados por alguma aresta e temos
uma árvore geradora mínima.
3. Usando as árvores binárias, desenvolva um grafo para
representar a quantidade de jogos necessários em um torneio
de vôlei com 16 inscritos.
A árvore binária, nesse caso, pode ser dita invertida, pois assumiremos
que os vértices pendentes são os 16 times inscritos e os vértices
internos mais a raiz, os jogos. Portanto, podemos representá-la como
a figura a seguir.
Resolução das atividades 159
v1
v3
v5
v7
v9
v11
v13
v15
v2
v4
v6
v8
v10
v12
v14
v16
v17
v18
v19
v20
v21
v22
v23
v24
v25
v26
v27
v28
v29
v30
v31
Então, teremos 16 vértices pendentes, 8 vértices internos na primeira
camada, 4 vértices internos na segunda camada e 2 vértices internos
na terceira camada. O jogo final é a raiz. Esse cálculo nos permite
escrever que, ao todo, temos 31(n) vértices e 30(n – 1) arestas.
M
A
RIN
A
V
A
RG
A
S
MARINA VARGAS
M
A
TEM
Á
TICA
PA
RA
CO
M
PUTA
ÇÃ
O
M A T E M Á T I C A
COMPUTAÇÃO
PARA
Código Logístico
I000122
ISBN 978-65-5821-071-9
9 7 8 6 5 5 8 2 1 0 7 1 9
M
A
RIN
A
V
A
RG
A
S
MARINA VARGAS
M
A
TEM
Á
TICA
PA
RA
CO
M
PUTA
ÇÃ
O
M A T E M Á T I C A
COMPUTAÇÃO
PARA
Código Logístico
I000122
ISBN 978-65-5821-071-9
9 7 8 6 5 5 8 2 1 0 7 1 9