---

import math
import numpy as np
import matplotlib.pyplot as plt

# =========================
# Вариант 20
# f(x) = x*sin(x)*arctg(x)
# [a, b] = [1, 2]
# Nmax = 10^6
# Критерии остановки:
#   1) для бисекции: |b-a| < eps_x
#   2) для касательных: |x_(n+1)-x_n| < eps_x
#   3) дополнительно: |f(x_(n+1)) - f(x_n)| < eps_f = 10^-15
# =========================

a = 1.0
b = 2.0
eps_x = 1e-14
eps_f = 1e-15
Nmax = 10**6


def f(x):
    return x * math.sin(x) * math.atan(x)


def df(x):
    return math.sin(x) * math.atan(x) + x * math.cos(x) * math.atan(x) + x * math.sin(x) / (1 + x * x)


def bisection_method(a, b):
    fa = f(a)
    fb = f(b)

    print('ПРОВЕРКА ДЛЯ БИСЕКЦИИ:')
    print(f'f(a) = f({a}) = {fa:.16f}')
    print(f'f(b) = f({b}) = {fb:.16f}')

    if fa * fb > 0:
        print('
Метод бисекции неприменим, потому что на [a,b] нет смены знака.')
        print('То есть f(a) * f(b) > 0.')
        return None, []

    print('
Смена знака есть, бисекцию можно применять.
')
    steps = []

    for n in range(1, Nmax + 1):
        c = (a + b) / 2.0
        fc = f(c)
        steps.append((n, a, b, c, fa, fb, fc, abs(b - a)))

        if abs(b - a) < eps_x:
            print(f'Корень найден методом бисекции: x ≈ {c:.16f}')
            print(f'Число итераций: {n}')
            return c, steps

        if fa * fc <= 0:
            b = c
            fb = fc
        else:
            a = c
            fa = fc

    return c, steps


def newton_method(x0):
    print('
ПРОВЕРКА ДЛЯ МЕТОДА КАСАТЕЛЬНЫХ:')
    print(f'Начальное приближение x0 = {x0}')

    steps = []
    x = x0

    for n in range(1, Nmax + 1):
        fx = f(x)
        dfx = df(x)

        if abs(dfx) < 1e-16:
            print('Производная слишком мала, метод остановлен.')
            return None, steps

        x_next = x - fx / dfx
        delta_x = abs(x_next - x)
        delta_f = abs(f(x_next) - f(x))

        steps.append((n, x, fx, dfx, x_next, delta_x, delta_f))

        if delta_x < eps_x or delta_f < eps_f:
            print(f'Корень найден методом касательных: x ≈ {x_next:.16f}')
            print(f'Число итераций: {n}')
            print(f'|x_(n+1)-x_n| = {delta_x:.3e}')
            print(f'|f(x_(n+1)) - f(x_n)| = {delta_f:.3e}')
            return x_next, steps

        x = x_next

    return x, steps


def draw_function():
    xs = np.linspace(a, b, 600)
    ys = [f(x) for x in xs]

    plt.figure(figsize=(10, 6))
    plt.plot(xs, ys, label='f(x) = x*sin(x)*arctg(x)', color='blue', linewidth=2)
    plt.axhline(0, color='black', linewidth=1)
    plt.axvline(a, color='gray', linestyle='--', alpha=0.5)
    plt.axvline(b, color='gray', linestyle='--', alpha=0.5)
    plt.scatter([a, b], [f(a), f(b)], color='red', zorder=5, label='Концы интервала')
    plt.title('График функции на [1, 2]')
    plt.xlabel('x')
    plt.ylabel('f(x)')
    plt.grid(True, alpha=0.3)
    plt.legend()
    plt.show()


def draw_bisection_visualization(steps):
    if not steps:
        print('
Для варианта 20 визуализация бисекции отсутствует,')
        print('потому что метод бисекции неприменим: нет смены знака на [1,2].')
        return

    xs = np.linspace(a, b, 600)
    ys = [f(x) for x in xs]

    plt.figure(figsize=(10, 6))
    plt.plot(xs, ys, color='blue', linewidth=2, label='f(x)')
    plt.axhline(0, color='black', linewidth=1)

    for i, step in enumerate(steps[:10]):
        n, left, right, mid, fa, fb, fm, width = step
        plt.axvline(mid, linestyle='--', alpha=0.4, label=f'c{i + 1}' if i == 0 else None)
        plt.scatter(mid, fm, color='red', s=25)

    plt.title('Метод бисекции: середины отрезков')
    plt.xlabel('x')
    plt.ylabel('f(x)')
    plt.grid(True, alpha=0.3)
    plt.legend()
    plt.show()


def draw_newton_visualization(x0, tangent_steps=6):
    xs = np.linspace(a, b, 600)
    ys = [f(x) for x in xs]

    plt.figure(figsize=(10, 6))
    plt.plot(xs, ys, color='blue', linewidth=2, label='f(x) = x*sin(x)*arctg(x)')
    plt.axhline(0, color='black', linewidth=1)

    x = x0
    for i in range(tangent_steps):
        fx = f(x)
        dfx = df(x)

        if abs(dfx) < 1e-16:
            break

        x_line = np.linspace(max(a, x - 0.4), min(b, x + 0.4), 100)
        y_line = fx + dfx * (x_line - x)

        plt.plot(x_line, y_line, '--', linewidth=1.5, label=f'Касательная {i + 1}')
        plt.scatter(x, fx, color='red', zorder=5)

        x_next = x - fx / dfx
        if a <= x_next <= b:
            plt.scatter(x_next, 0, color='green', zorder=5)

        delta_x = abs(x_next - x)
        delta_f = abs(f(x_next) - f(x)) if abs(x_next) < 1e6 else float('inf')

        if delta_x < eps_x or delta_f < eps_f:
            break

        x = x_next

    plt.title('Метод касательных: все касательные из начальной точки')
    plt.xlabel('x')
    plt.ylabel('f(x)')
    plt.grid(True, alpha=0.3)
    plt.legend()
    plt.show()


# =========================
# ОСНОВНАЯ ЧАСТЬ
# =========================

print('ВАРИАНТ 20')
print('f(x) = x*sin(x)*arctg(x)')
print(f'Интервал: [{a}, {b}]')
print(f'Nmax = {Nmax}')
print(f'eps_x = {eps_x}')
print(f'eps_f = {eps_f}')
print('-' * 60)

fa = f(a)
fb = f(b)

print(f'f({a}) = {fa:.16f}')
print(f'f({b}) = {fb:.16f}')

bis_steps = []
newton_steps = []

if fa * fb > 0:
    print('
На отрезке [1,2] нет смены знака.')
    print('Следовательно, корня на заданном интервале нет.')
    print('Метод бисекции неприменим.')
    print('Метод касательных можно только визуализировать,')
    print('но корень на [1,2] эта функция не имеет.')
else:
    root_bis, bis_steps = bisection_method(a, b)
    root_newton, newton_steps = newton_method((a + b) / 2)

print('
Построение графиков...')
draw_function()
draw_bisection_visualization(bis_steps)
draw_newton_visualization(1.5, tangent_steps=6)