Banach Spaces

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Simple finite-dimensional vector with p-norms
5
struct Vec {
6
    vector<double> a;
7
    explicit Vec(size_t n=0, double v=0.0): a(n, v) {}
8
    explicit Vec(const vector<double>& x): a(x) {}
9
10
    size_t dim() const { return a.size(); }
11
12
    // p-norm for 1 <= p < infinity
13
    double norm_p(double p) const {
14
        if (p < 1.0 || isinf(p)) throw invalid_argument("p must satisfy 1 <= p < infinity here");
15
        long double s = 0.0L;
16
        for (double v : a) s += powl(fabsl((long double)v), (long double)p);
17
        return pow((long double)s, 1.0L/(long double)p);
18
    }
19
20
    // Infinity norm (max absolute entry)
21
    double norm_inf() const {
22
        long double m = 0.0L;
23
        for (double v : a) m = max(m, fabsl((long double)v));
24
        return (double)m;
25
    }
26
27
    // Euclidean norm shortcut
28
    double norm2() const { return norm_p(2.0); }
29
30
    // Distance induced by a chosen norm (here Euclidean)
31
    static double dist2(const Vec& x, const Vec& y) {
32
        if (x.dim() != y.dim()) throw invalid_argument("dim mismatch");
33
        long double s = 0.0L;
34
        for (size_t i=0;i<x.a.size();++i) {
35
            long double d = (long double)x.a[i] - (long double)y.a[i];
36
            s += d*d;
37
        }
38
        return sqrt((double)s);
39
    }
40
};
41
42
// Brute-force numerical check: does the tail of the sequence look Cauchy?
43
// Returns true if there exists N such that for all m,n >= N, dist(x_m, x_n) <= eps.
44
// For a finite list x[0..K-1], we search N in [0..K-1] and test all tail pairs.
45
// Note: This is a finite, numerical surrogate for the mathematical definition.
46
bool isCauchyEuclidean(const vector<Vec>& xs, double eps, int& N_out) {
47
    int K = (int)xs.size();
48
    for (int N = 0; N < K; ++N) {
49
        bool ok = true;
50
        for (int m = N; m < K && ok; ++m) {
51
            for (int n = m; n < K; ++n) {
52
                if (Vec::dist2(xs[m], xs[n]) > eps) { ok = false; break; }
53
            }
54
        }
55
        if (ok) { N_out = N; return true; }
56
    }
57
    return false;
58
}
59
60
int main() {
61
    cout.setf(std::ios::fixed); cout<<setprecision(6);
62
63
    // Demonstrate norms in R^3
64
    Vec v({3.0, -4.0, 12.0});
65
    cout << "||v||_1 = " << v.norm_p(1.0) << "\n";
66
    cout << "||v||_2 = " << v.norm2() << "\n";
67
    cout << "||v||_inf = " << v.norm_inf() << "\n";
68
69
    // Build a sequence in R^1: partial sums of a geometric series with r=0.5 (Cauchy)
70
    vector<Vec> seqC;
71
    double r = 0.5;
72
    double s = 0.0;
73
    for (int k = 0; k < 30; ++k) {
74
        s += pow(r, k); // partial sum
75
        seqC.emplace_back(vector<double>{s});
76
    }
77
78
    int N; bool cauchy = isCauchyEuclidean(seqC, 1e-3, N);
79
    cout << "Geometric partial sums Cauchy? " << (cauchy?"yes":"no")
80
         << ", witness N = " << (cauchy?N:-1) << "\n";
81
82
    // A non-Cauchy sequence in R^1: x_n = n (diverges)
83
    vector<Vec> seqNC;
84
    for (int k = 0; k < 30; ++k) seqNC.emplace_back(vector<double>{(double)k});
85
    bool cauchy2 = isCauchyEuclidean(seqNC, 1e-3, N);
86
    cout << "Sequence x_n=n Cauchy? " << (cauchy2?"yes":"no") << "\n";
87
88
    return 0;
89
}
90

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Simple 1D fixed-point solver using Banach's theorem
5
// If f is a contraction with constant L in |.| and maps a closed interval into itself,
6
// this iteration converges to the unique fixed point.
7
struct FixedPointResult {
8
    double root;
9
    int iters;
10
    bool converged;
11
};
12
13
FixedPointResult banach_fixed_point(function<double(double)> f,
14
                                    double x0,
15
                                    double L,       // contraction constant (must be < 1)
16
                                    double tol,     // desired bound on |x - x*|
17
                                    int max_iter) {
18
    if (!(L > 0 && L < 1)) throw invalid_argument("L must be in (0,1)");
19
    double x_prev = x0;
20
    double x = f(x_prev);
21
    int k = 1;
22
    // A posteriori error bound: |x_k - x*| <= (L/(1-L)) |x_k - x_{k-1}|.
23
    while (k < max_iter) {
24
        double step = fabs(x - x_prev);
25
        double err_bound = (L / (1.0 - L)) * step;
26
        if (err_bound <= tol) {
27
            return {x, k, true};
28
        }
29
        x_prev = x;
30
        x = f(x_prev);
31
        ++k;
32
    }
33
    return {x, k, false};
34
}
35
36
int main() {
37
    cout.setf(std::ios::fixed); cout<<setprecision(8);
38
39
    // Example 1: Solve x = cos(x) on R using contraction on [0,1]
40
    // On [0,1], |cos'(x)| = | -sin(x) | <= sin(1) ~ 0.84147 < 1, so L can be 0.85 safely.
41
    auto f1 = [](double x){ return cos(x); };
42
    FixedPointResult r1 = banach_fixed_point(f1, 0.5, 0.85, 1e-8, 100);
43
    cout << "x = cos(x): root ~ " << r1.root << ", iters = " << r1.iters
44
         << ", converged = " << (r1.converged?"yes":"no") << "\n";
45
46
    // Example 2: Linear contraction x = a x + b with |a|<1 has fixed point b/(1-a)
47
    double a = 0.3, b = 2.0; // L = |a|
48
    auto f2 = [=](double x){ return a*x + b; };
49
    FixedPointResult r2 = banach_fixed_point(f2, 0.0, fabs(a), 1e-10, 100);
50
    cout << "x = 0.3 x + 2 => root ~ " << r2.root << " (true = " << b/(1-a) << ")\n";
51
52
    return 0;
53
}
54

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Generate random vectors and estimate constants c, C such that
5
// c * ||x||_2 <= ||x||_1 <= C * ||x||_2 for sampled x != 0.
6
// In finite dimensions, such c, C > 0 exist (exact values depend on n),
7
// and this experiment illustrates equivalence of norms numerically.
8
9
struct Ratios { double min_r, max_r; };
10
11
static double norm1(const vector<double>& x){ double s=0; for(double v:x) s+=fabs(v); return s; }
12
static double norm2(const vector<double>& x){ long double s=0; for(double v:x) s+=(long double)v*v; return sqrt((double)s); }
13
14
Ratios estimate_ratios(int n, int samples, unsigned seed=42) {
15
    mt19937 rng(seed);
16
    normal_distribution<double> N01(0.0,1.0);
17
    double min_r = numeric_limits<double>::infinity();
18
    double max_r = 0.0;
19
    for (int k=0;k<samples;++k) {
20
        vector<double> x(n);
21
        for (int i=0;i<n;++i) x[i] = N01(rng);
22
        double n2 = norm2(x);
23
        if (n2 == 0) { --k; continue; } // resample zero vector
24
        double n1 = norm1(x);
25
        double r = n1 / n2; // ratio ||x||_1 / ||x||_2
26
        min_r = min(min_r, r);
27
        max_r = max(max_r, r);
28
    }
29
    return {min_r, max_r};
30
}
31
32
int main(){
33
    cout.setf(std::ios::fixed); cout<<setprecision(6);
34
    int n = 10;
35
    int M = 20000;
36
    auto rs = estimate_ratios(n, M);
37
    cout << "Estimated c, C with " << M << " samples in R^" << n << ":\n";
38
    cout << "c ~ " << rs.min_r << ", C ~ " << rs.max_r << " so c*||x||_2 <= ||x||_1 <= C*||x||_2.\n";
39
    // Theoretical bounds: For any x in R^n, ||x||_2 <= ||x||_1 <= sqrt(n) ||x||_2.
40
    cout << "Theoretical: 1*||x||_2 <= ||x||_1 <= sqrt(n)*||x||_2 = " << sqrt((double)n) << " * ||x||_2.\n";
41
    return 0;
42
}
43